Interview challenge · easy · array, hash-map
Two Sum
El reto
El enunciado va en inglés, igual que en el vídeo.
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution and you may not use the same element twice.
Example
nums = [2, 7, 11, 15], target = 9 -> [0, 1] (2 + 7 = 9)
nums = [3, 2, 4], target = 6 -> [1, 2]
nums = [3, 3], target = 6 -> [0, 1]Idea: one pass with a hash map. For each number look up target - n; if it was seen before, you are done. Otherwise store the number with its index. Time O(n), space O(n).
La solución
# Two Sum - ayotl.dev
def two_sum(nums, target):
seen = {} # value -> its index
for i, n in enumerate(nums):
rest = target - n # what we need
if rest in seen:
return [seen[rest], i]
seen[n] = i
return []
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([3, 3], 6))
$ python3 two_sum.py
[0, 1]
[1, 2]
[0, 1]