Easy Complement Map Hash Maps
In plain English: Find two numbers in an unsorted list that add up to a target and return their indices.
Instead of checking all pairs O(n²), store each value in a hashmap — then lookup for the complement is O(1).
Prompt
Given unsorted array a and target t, return indices of the pair that sums to t.
Try to write it from scratch before scrolling down.
Solution
def two_sum(a, t):
seen = {}
for i, x in enumerate(a):
# check complement before storing
if t - x in seen:
return [seen[t - x], i]
seen[x] = i
return []
# Test: two_sum([2,7,11,15], 9) == [0, 1]