Как устроено решение задачи поиска пары чисел с заданной суммой?

Задача: найти в массиве пару чисел, сумма которых равна заданному числу.

Классическое решение:

• Перебор всех пар — O(n²), неэффективно.

Оптимальное решение с использованием хэш-таблицы (словаря):

1. Создаем пустую хэш-таблицу.
2. Проходим по массиву, для каждого элемента x проверяем, есть ли в таблице число target - x.
3. Если есть — нашли пару.
4. Если нет — добавляем x в таблицу и идем дальше.

Сложность: O(n) по времени и O(n) по памяти.

Пример на Python:

def find_pair(nums, target):
    seen = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            return (complement, num)
        seen.add(num)
    return None

Это решение эффективно и широко используется в задачах поиска пар с заданной суммой.