GIVEN NUMBERS AND A TARGET, FIND THE TWO THAT ADD UP TO IT. THE TRICK: DON'T CHECK EVERY PAIR. WALK ONCE, AND ASK IF EACH NUMBER'S PARTNER WAS ALREADY SEEN.
EACH NUMBER NEEDS ONE PARTNER: TARGET MINUS ITSELF. REMEMBER EVERY NUMBER YOU PASS. THE ANSWER IS THE FIRST PARTNER ALREADY REMEMBERED.
ONE PASS. BLUE IS THE NUMBER WE ARE ON. TAN TILES ARE REMEMBERED. THE GOLD PAIR IS THE ANSWER.
1def two_sum(nums, target):2 seen = {} # value -> index3 for i, num in enumerate(nums):4 need = target - num5 if need in seen:6 return [seen[need], i]7 seen[num] = i
ONE WALK THROUGH THE LIST. EACH NUMBER DOES A SINGLE FAST LOOKUP IN THE MAP.
THE MAP CAN HOLD EVERY NUMBER SEEN. WE TRADE A LITTLE MEMORY FOR A LOT OF SPEED.