Проходите массив один раз и храните уже встреченные числа с индексами. Для каждого x ищите target − x до добавления x, чтобы не использовать один элемент дважды.
Дан массив чисел, найти индексы двух элементов, дающих в сумме target.
Проходите массив один раз и храните уже встреченные числа с индексами. Для каждого x ищите target − x до добавления x, чтобы не использовать один элемент дважды.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Дан массив чисел, найти индексы двух элементов, дающих в сумме target.
Известно что такая пара элементов в этом массиве существует и единственна.
Ответ
Проходите массив один раз и храните уже встреченные числа с индексами. Для каждого x ищите target − x до добавления x, чтобы не использовать один элемент дважды.
def two_sum(nums, target):
seen = {}
for i, value in enumerate(nums):
other = target - value
if other in seen:
return seen[other], i
seen[value] = i
raise ValueError('Pair not found')
Для целых чисел и обычной хеш-таблицы ожидаемое время O(n), дополнительная память O(n). Пара одинаковых значений, например [3, 3] при target 6, обрабатывается правильно: второй элемент находит первый. По условию ответ существует и единственен; исключение защищает случай нарушения этого контракта.