Как найти два числа, дающих заданную сумму (Two Sum)?

Условие задачи

Дан список чисел и target. Нужно найти индексы двух разных элементов, сумма которых равна target. Обычно предполагается, что решение существует и каждый элемент нельзя использовать дважды.

Наивное решение

Можно проверить каждую пару через два вложенных цикла. Это просто, но временная сложность будет O(n²).

def two_sum_bruteforce(items: list[int], target: int) -> tuple[int, int] | None:
    for first in range(len(items)):
        for second in range(first + 1, len(items)):
            if items[first] + items[second] == target:
                return first, second

    return None

Оптимальное решение через dict

Во время одного прохода сохраняем уже встреченные числа и их индексы. Для текущего числа value ищем target - value.

def two_sum(items: list[int], target: int) -> tuple[int, int] | None:
    seen = {}

    for index, value in enumerate(items):
        complement = target - value

        if complement in seen:
            return seen[complement], index

        seen[value] = index

    return None

Пример

numbers = [2, 7, 11, 15]
print(two_sum(numbers, 9))
# (0, 1)

Почему сначала проверяем complement

Сначала ищем complement среди уже обработанных элементов, а потом сохраняем текущее значение. Это не позволяет использовать один элемент дважды в случае, когда target = 2 × value.

Сложность

Поиск ключа и вставка в словарь в среднем занимают O(1). Поэтому один проход по списку даёт временную сложность O(n), а словарь требует O(n) дополнительной памяти.

Как ответить на собеседовании

Для Two Sum использую хеш-таблицу: для каждого числа вычисляю complement, равный target - value, и проверяю, был ли он среди предыдущих значений. Если был, возвращаю его индекс и текущий индекс. Это решение работает за O(n) времени и использует O(n) памяти.