Two Sum (Сумма двух чисел)
Описание: Дан массив целых чисел nums и целевое значение target. Верните индексы двух чисел из массива, сумма которых равна target. Предполагается, что существует ровно одно решение, и нельзя использовать один и тот же элемент дважды.
Вы можете вернуть ответ в любом порядке.
Пример 1:
Вход: nums = [3,4,5,6], target = 7
Выход: [0,1]
Объяснение: nums[0] + nums[1] = 3 + 4 = 7
Пример 2:
Вход: nums = [4,5,6], target = 10
Выход: [0,2]
Объяснение: nums[0] + nums[2] = 4 + 6 = 10
Ограничения:
2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Существует только одно правильное решение
Рекомендуемая временная и пространственная сложность
Стремитесь к решению со временной сложностью O(n) и пространственной сложностью O(n), где n - длина массива nums.
Подсказка 1
Прямолинейное решение - использовать два вложенных цикла для перебора всех возможных пар чисел. Это даст временную сложность O(n²). Можете ли вы придумать более эффективное решение?
Подсказка 2
Для каждого числа x, вы ищете другое число y, такое что x + y = target. Другими словами, вы ищете complement = target - x. Как можно быстро проверить, существует ли complement в массиве?
Подсказка 3
Хеш-таблица позволяет выполнять поиск за O(1). Вы можете хранить каждое просмотренное число и его индекс в хеш-таблице. Для текущего числа проверяйте, есть ли в таблице complement.