Задача Two Sum на Python
В этом уроке вы решите задачу Two Sum: найдёте два элемента, сумма которых равна заданному значению, за один проход по списку.
Введение
Какую задачу это решает
Есть список цен и бюджет: какие два товара вместе стоят ровно столько, сколько бюджет? Перебор всех пар работает, но занимает около n² / 2 сравнений. Если запоминать уже увиденное, задачу можно решить за один проход.
Пример из жизни
Задача Two Sum похожа на покупки с точной суммой. Глядя на каждый ценник, вы считаете, сколько ещё не хватает, и заглядываете в записи: встречался ли уже товар ровно с такой ценой? Если да, пара найдена. Если нет, вы записываете эту цену и где её видели, и идёте дальше.
complement = target - value🤔 Сколько ещё не хватаетif complement in seen:📋 Есть ли такая цена в моих записях?return [seen[complement], index]🛍️ Пара найдена: обе позицииseen[value] = index✍️ Записать эту цену и её позицию, идти дальшеВ задаче Two Sum (сумма двух) нужно найти позиции двух чисел в списке, сумма которых равна цели. Словарь уже просмотренных значений решает её за один проход, за время O(n).
Главное
complement = target - value- значение, которого не хватает до пары.seenхранит для каждого уже просмотренного значения его индекс, поэтому поиск в нём быстрый.if complement in seen:находит партнёра среди предыдущих значений.seen[value] = indexвыполняется после проверки, поэтому значение никогда не составит пару само с собой.- При цели 9 значение 7 находит партнёра 2 по индексу 0, и получается
[0, 1].
Когда это нужно?
- Поиск пар с заданной суммой или разностью.
- Знакомство с тем, как хеш-таблица позволяет выиграть в скорости ценой памяти.
- Очень частый вопрос на собеседованиях и основа для 3-Sum и похожих задач.
Когда это не нужно
- Данные отсортированы, а памяти мало: метод двух указателей, идущих с обоих концов, обходится без дополнительной памяти.
- Нужны все пары, а не одна: собирайте результаты, а не возвращайте первое совпадение.
Пример кода
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Результат выполнения
[0, 1]
Разбор кода
Словарь seen запоминает уже пройденные значения вместе с их позициями. Для каждого элемента программа вычисляет дополнение complement = target - value и проверяет, есть ли оно уже в seen. Поиск в словаре стоит O(1), поэтому весь алгоритм работает за O(n) с O(n) дополнительной памяти.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Сохранение до проверки
Значение может составить пару само с собой: например, 3 + 3 = 6, хотя тройка в списке всего одна.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
Все задачи