Дан массив чисел и целевое значение target. Верните индексы двух элементов, сумма которых равна target. Один элемент дважды использовать нельзя.
Короткий ответ
- Перебор пар даёт O(n^2) — назвать и улучшить
- Храним просмотренные значения и их индексы в словаре
- Для каждого x ищем target - x в словаре
- Один проход: сначала проверка, потом вставка
- Порядок проверка-вставка исключает использование элемента дважды
- Дубликаты в массиве обрабатываются корректно сами собой
Один проход со словарём «значение → индекс» решает задачу за O(n) по времени и O(n) по памяти.
Как сказать вслух
пример ответаНаивно можно перебрать все пары за квадрат, но я сразу предложу словарь. Иду по массиву и для каждого числа проверяю, видел ли я уже его дополнение до target. Если видел — возвращаю пару индексов, если нет — кладу текущее число в словарь и иду дальше.
Подробный ответ
Основной ответ
Брутфорс проверяет все пары за O(n^2). Оптимизация — хэш-таблица: идём по массиву один раз, на каждом шаге вычисляем дополнение target - x и смотрим, встречалось ли оно раньше. Если да — ответ готов: сохранённый индекс дополнения и текущий индекс. Если нет — записываем x с его индексом в словарь. Критичен порядок: сначала проверка, потом вставка текущего элемента — так элемент не может «найти сам себя» при target, равном удвоенному значению. Каждая операция со словарём в среднем O(1), итого O(n) времени и O(n) дополнительной памяти. Для отсортированного массива есть альтернатива — два указателя за O(1) памяти, но она возвращает значения, а не исходные индексы.
Ключевые моменты
- Дополнение вместо пары. Вместо поиска пары (x, y) ищем для каждого x заранее известное значение target - x — это сводит задачу к поиску в словаре.
- Порядок операций. Проверка до вставки гарантирует, что найденное дополнение — другой элемент массива, даже если значения совпадают.
- Сложность. O(n) времени в среднем, O(n) памяти; худший случай хэш-таблицы теоретически хуже, но на собеседовании принимается средний.
- Вариант с указателями. Если массив отсортирован или индексы не нужны, два указателя с концов дают O(n log n) или O(n) без дополнительной памяти.
Практический контекст
Это разогревочная задача: интервьюер смотрит на чистоту кода, умение назвать сложность и проговорить переход от O(n^2) к O(n). Уточните: может ли быть несколько ответов, гарантировано ли существование решения, бывают ли отрицательные числа (бывают — алгоритму всё равно). Классическая ловушка-проверка: «а если target = 6 и в массиве одна шестёрка пополам — 3?»
Пример кода
def two_sum(nums, target):
seen = {} # значение -> индекс
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([3, 2, 4], 6) == [1, 2]Частые ошибки
- Сначала заполняют весь словарь, потом ищут — элемент находит сам себя при x = target / 2
- Возвращают значения вместо индексов или путают порядок индексов
- Не могут объяснить, почему средняя сложность поиска в хэш-таблице O(1)