#Array#Hash Table
Дан массив целых чисел nums и целевое число target, вернуть индексы двух чисел таким образом, чтобы они в сумме давали target.
Можно предположить, что каждый вход будет иметь ровно одно решение, и нельзя использовать один и тот же элемент дважды.
Вы можете вернуть ответ в любом порядке.
Пример 1:
Вход: nums = [2,7,11,15], target = 9
Выход: [0,1]
Объяснение: поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1].
Пример 2:
Вход: nums = [3,2,4], цель = 6
Выход: [1,2]
Пример 3:
Вход: nums = [3,3], цель = 6
Выход: [0,1]
Ограничения:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= цель <= 109
Существует только один допустимый ответ.
Продолжение: Можете ли вы придумать алгоритм, который имеет временную сложность меньше O(n2)?
Подсказка 1
Действительно грубым методом был бы поиск всех возможных пар чисел, но это было бы слишком медленно. Опять же, лучше всего попробовать решения методом грубой силы просто для полноты. Именно из этих решений методом грубой силы вы можете придумать оптимизации.
Подсказка 2
Итак, если мы фиксируем одно из чисел, скажем x, нам придется сканировать весь массив, чтобы найти следующее число y, которое равно value - x, где value - входной параметр. Можем ли мы как-то изменить наш массив, чтобы этот поиск стал быстрее?
Подсказка 3
Вторая мысль: не меняя массив, можем ли мы как-то использовать дополнительное пространство? Например, хэш-карту для ускорения поиска?
Пример решения на go
func twoSum(nums []int, target int) []int {
r:=make(map[int]int,0)
for i, num:=range nums{
calc:=target-num
index,ok:=r[num]
if ok {
return []int{index,i}
}
r[calc] = i
}
return nil
}
Пишите в комментариях ваши решения.