Поиск парных индексов с заданной суммой

Условие

Дан массив целых чисел arr и целое число targetSum. Необходимо вернуть индексы двух элементов, сумма которых равна targetSum.

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

Порядок индексов в возвращаемом массиве не важен.

Пример 1:

Input: arr = [2, 7, 11, 15], targetSum = 9
Output: [0, 1]
Explanation: arr[0] + arr[1] == 9, поэтому возвращаем [0, 1].

Пример 2:

Input: arr = [3, 2, 4], targetSum = 6
Output: [1, 2]

Ответ

Храните словарь число → ранее встреченный индекс. Для каждого элемента ищите targetSum − элемент, проверяя до добавления текущего индекса.

def two_sum(arr, targetSum):
    seen = {}
    for index, value in enumerate(arr):
        complement = targetSum - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    raise ValueError('Пара не найдена')

По условию последняя строка недостижима для корректного входа. Проверка до записи гарантирует различные индексы. Дубликаты обрабатываются правильно: для [3, 3] и суммы 6 второй элемент найдёт первый.

Ожидаемое время O(n), дополнительная память O(n). Важно проверять complement in seen, а не истинность сохранённого индекса: индекс 0 также является корректным.