Найди два числа с заданной суммой

Two Sum — одна из самых частых задач на алгоритмических секциях. Наивное решение приходит сразу, но оно квадратичное, и собеседующий ждёт, что ты его ускоришь. Если массив можно отсортировать — красивый ответ даёт метод двух указателей.

Задача

Дан массив чисел и целевое число k. Нужно найти пару элементов, сумма которых равна k, и вернуть их (или сообщить, что пары нет).

Пример из задания: arr = [-9, -7, -6, -1, -1, 3], k = 2 — подходящая пара -1 и 3.

Решение

def two_sum(arr, k):
    nums = sorted(arr)
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == k:
            return nums[left], nums[right]
        if s < k:
            left += 1
        else:
            right -= 1
    return None


cases = [
    ([-9, -7, -6, -1, -1, 3], 2),
    ([2, 7, 11, 15], 9),
    ([1, 2, 3], 100),
]
for arr, k in cases:
    print(f"arr={arr}, k={k} -> {two_sum(arr, k)}")

Разбор

Наивное решение — двойной цикл: перебрать все пары (i, j) и проверить, даёт ли какая-то в сумме k. Работает, но это O(n²): на массиве из десятков тысяч чисел уже больно. С этого варианта нормально начать, но останавливаться на нём нельзя.

Метод двух указателей требует одного условия — массив должен быть отсортирован (sorted(arr), это O(n log n)). Дальше ставим один указатель в начало (left, самое маленькое число), другой в конец (right, самое большое) и смотрим на их сумму:

• сумма равна k — нашли пару, возвращаем;
• сумма меньше k — нужно больше, двигаем left вправо, к бо́льшим числам;
• сумма больше k — нужно меньше, двигаем right влево, к меньшим.

Почему это работает и ничего не пропускает. Массив отсортирован, поэтому сдвиг left может только увеличить сумму, а сдвиг right — только уменьшить. Каждым шагом мы отбрасываем вариант, который заведомо не подойдёт: если даже с самым большим right сумма мала — значит, текущий left в паре ни с кем не даст k, его можно навсегда отпустить. Указатели идут навстречу и вместе делают не больше n шагов — это O(n) после сортировки.

Краевой случай «пары нет» — как в третьем тесте: указатели сходятся (left встречает right), цикл while left < right завершается, возвращаем None. Обработать этот случай явно обязательно, иначе на входе без ответа функция вернёт мусор или упадёт.

Сравнение подходов, которое стоит проговорить. Два указателя дают O(n log n) из-за сортировки, но не тратят лишнюю память. Альтернатива — хеш-множество: идём по массиву один раз, для каждого числа x проверяем, встречали ли уже k - x. Это O(n) по времени, но O(n) по памяти под множество, и сортировка не нужна — то есть хеш-подход выигрывает, когда массив уже неотсортирован и память не жалко. Хороший ответ — назвать оба и объяснить размен «время против памяти и сортировки».

Тот же приём одного прохода по массиву лежит в основе задачи про скользящее среднее.

Ожидаемый результат

arr=[-9, -7, -6, -1, -1, 3], k=2 -> (-1, 3)
arr=[2, 7, 11, 15], k=9 -> (2, 7)
arr=[1, 2, 3], k=100 -> None