Two Sum
Тебе дан список целых чисел и целевое значение. Ровно два числа из списка в сумме дают целевое значение, и твоя задача — указать их позиции.
Возьми nums = [3, 8, 12, 5] и target = 17. Значение 12 находится по индексу 2, а 5 — по индексу 3, и 12 + 5 = 17, поэтому ответ — [2, 3].
Эти два числа должны находиться в разных позициях. В [4, 2, 6] при target = 8 нельзя использовать число 4 дважды; ответ — [1, 2], потому что 2 + 6 = 8. Однако одно и то же значение может встретиться дважды: в [7, 3, 7] при target = 14 ответ — [0, 2].
Напишите функцию с именем twoSum, которая получает массив целых чисел nums и целое число target и возвращает массив из двух индексов [i, j], таких что nums[i] + nums[j] равно target.
Индексы должны указывать на две разные позиции и возвращаться в порядке возрастания (i меньше j). Для каждого входного набора существует ровно одна такая пара.
Ограничения: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Функция
- arg1integer-array
- arg2integer
- Возвращаетinteger-array
Примеры
- Ввод
- arg1 = [3, 8, 12, 5]arg2 = 17
- Вывод
- [2, 3]
- Ввод
- arg1 = [6, 1, 4, 10]arg2 = 7
- Вывод
- [0, 1]
- Ввод
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Вывод
- [1, 2]
+13 скрытых тестов при отправке
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Перебирать каждую пару с помощью двух вложенных циклов правильно, но для 10 000 чисел это около 50 миллионов проверок. Сможешь найти для каждого числа пару, не просматривая список повторно?
Когда ты остановился на значении
x, ты уже знаешь, какое значение дополнит пару: целевое значение минусx. Единственный вопрос — встречалось ли тебе это значение раньше и по какому индексу.Пройдите по списку один раз и сохраняйте в хеш-таблице каждое уже пройденное значение и его индекс. На каждой позиции сначала найдите недостающее парное значение; если оно есть в таблице, значит, у вас есть оба индекса. В противном случае сохраните текущее значение и двигайтесь дальше. Поиск перед сохранением не позволяет числу образовать пару с самим собой.
Полный разбор этой задачи скоро появится.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def twoSum(nums, target):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
arg1 = [3, 8, 12, 5] arg2 = 17
Ожидается
[2, 3]