Алгоритмы на Python

Задача Two Sum на Python

В этом уроке вы решите задачу Two Sum: найдёте два элемента, сумма которых равна заданному значению, за один проход по списку.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Есть список цен и бюджет: какие два товара вместе стоят ровно столько, сколько бюджет? Перебор всех пар работает, но занимает около n² / 2 сравнений. Если запоминать уже увиденное, задачу можно решить за один проход.

Пример из жизни

Задача Two Sum похожа на покупки с точной суммой. Глядя на каждый ценник, вы считаете, сколько ещё не хватает, и заглядываете в записи: встречался ли уже товар ровно с такой ценой? Если да, пара найдена. Если нет, вы записываете эту цену и где её видели, и идёте дальше.

От покупок с точной суммой к коду
complement = target - value🤔 Сколько ещё не хватает
if complement in seen:📋 Есть ли такая цена в моих записях?
return [seen[complement], index]🛍️ Пара найдена: обе позиции
seen[value] = index✍️ Записать эту цену и её позицию, идти дальше
Ищите недостающую цену в записях, а не перебирайте все пары.
Одним предложением

В задаче Two Sum (сумма двух) нужно найти позиции двух чисел в списке, сумма которых равна цели. Словарь уже просмотренных значений решает её за один проход, за время O(n).

Главное

  1. complement = target - value - значение, которого не хватает до пары.
  2. seen хранит для каждого уже просмотренного значения его индекс, поэтому поиск в нём быстрый.
  3. if complement in seen: находит партнёра среди предыдущих значений.
  4. seen[value] = index выполняется после проверки, поэтому значение никогда не составит пару само с собой.
  5. При цели 9 значение 7 находит партнёра 2 по индексу 0, и получается [0, 1].

Когда это нужно?

  • Поиск пар с заданной суммой или разностью.
  • Знакомство с тем, как хеш-таблица позволяет выиграть в скорости ценой памяти.
  • Очень частый вопрос на собеседованиях и основа для 3-Sum и похожих задач.

Когда это не нужно

  • Данные отсортированы, а памяти мало: метод двух указателей, идущих с обоих концов, обходится без дополнительной памяти.
  • Нужны все пары, а не одна: собирайте результаты, а не возвращайте первое совпадение.

Пример кода

Запустить код →
main.py
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.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Сохранение до проверки

Значение может составить пару само с собой: например, 3 + 3 = 6, хотя тройка в списке всего одна.

Ошибка
seen[value] = index
if target - value in seen:
Исправление
if target - value in seen:
    return [seen[target - value], index]
seen[value] = index

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи