1. Two Sum

Условие

1. Two Sum

Дано массив целых чисел nums и целевое число target, верните индексы двух чисел так, чтобы они в сумме давали target.

Вы можете предположить, что в каждом входе есть ровно одно решение, и не можете использовать один и тот же элемент дважды.

Ответ можно вернуть в любом порядке.

Пример 1:

Ввод: nums = [2,7,11,15], target = 9 Вывод: [0,1] Объяснение: потому что nums[0] + nums[1] == 9, мы возвращаем [0, 1].

Пример 2:

Ввод: nums = [3,2,4], target = 6 Вывод: [1,2]

Пример 3:

Ввод: nums = [3,3], target = 6 Вывод: [0,1]

Ответ

Идите по массиву и храните уже встреченные числа с индексами. Для каждого x ищите target - x; так решение находится за O(n) ожидаемого времени.

def two_sum(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], i]
        seen[value] = i
    raise ValueError("Пара не найдена")

Проверка выполняется до добавления текущего элемента, поэтому один индекс нельзя использовать дважды. Для [3, 3] и цели 6 второй элемент найдёт первый. Дополнительная память — O(n); ожидаемая оценка времени предполагает обычную работу хеш-таблицы.