Interview challenge · easy · array, hash-map
Two Sum
The challenge
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).
The solution
# 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]