Определение индексов пары чисел с требуемой суммой

Условие

Дан массив целых чисел arr и целевое значение need. Требуется найти два элемента, чья сумма равна need, и вернуть индексы этих элементов в массиве. Гарантируется, что входные данные корректны и решение существует. Input: numbers = [2, 7, 11, 15], target = 9 Output: [0, 1]

Ответ

Храните в хеш-таблице уже встреченные значения и их индексы. Для каждого числа ищите need−number до добавления текущего элемента, чтобы не использовать один индекс дважды.

Пример на Python:

def two_sum(arr, need):
    seen = {}
    for i, value in enumerate(arr):
        other = need - value
        if other in seen:
            return [seen[other], i]
        seen[value] = i
    raise ValueError('pair not found')

Для [2,7,11,15] и 9 результат [0,1]. Пара [3,3] тоже работает благодаря проверке до вставки. Среднее время O(n), дополнительная память O(n); ветка ошибки оставлена защитно, хотя условие гарантирует решение.