Определить индексы пары элементов, сумма которых равна заданному числу

Условие

Даны два входных параметра: массив целых чисел numbers и целое значение targetSum. Необходимо найти два различных индекса i и j из массива numbers, такие что numbers[i] + numbers[j] == targetSum, и вернуть их в виде массива [i, j]. Если такая пара не существует, можно вернуть пустой массив или null в зависимости от требований задачи.

Пример:

numbers = [2, 7, 11, 15]
targetSum = 9
# Ожидаемый результат: [0, 1] because numbers[0] + numbers[1] = 2 + 7 = 9

Требования к решению:

• Время работы должно быть O(n) или лучше.
• Допустимы любые корректные реализации на выбранном языке.

Ответ

За один проход храните индексы ранее встреченных чисел и ищите дополнение до targetSum. Если пары нет, верните пустой список.

def find_pair_indices(numbers, targetSum):
    seen = {}
    for index, number in enumerate(numbers):
        complement = targetSum - number
        if complement in seen:
            return [seen[complement], index]
        seen[number] = index
    return []

Для [2, 7, 11, 15] и 9 вернутся [0, 1]. Два равных значения допускаются на разных позициях, но текущая позиция не используется дважды, потому что проверка предшествует добавлению.

Ожидаемая сложность O(n), память O(n). Это средняя оценка хеш-таблицы; для произвольного неупорядоченного входа чтения O(n) элементов в худшем случае избежать нельзя.