Find the two numbers that add up to the target. Walk once, and for each number look up the partner you need in a map of what you've seen.
▼The problem
Given a list of numbers and a target, return the indices of the two numbers that add up to the target. There is exactly one answer, and the same element can't be used twice.
Example: nums = [5, 9, 2, 8, 3, 6], target = 12 → [1, 4] (9 + 3).
The solution
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = iTranscript
Two Sum. Given a list of numbers and a target, return the indices of the two that add up to it. There's exactly one answer, and you can't use the same number twice.
Take five, nine, two, eight, three, six, with a target of twelve. You could check every pair, but that's about n squared checks.
Instead, walk the list once, and keep a map of every number you've seen, with its index. At each number, ask: have I seen the target minus this one? If yes, you're done. If not, store it and move on.
Five needs seven: not seen, store it. Nine needs three: store it. Two needs ten. Eight needs four. Three needs nine, and nine is in the map, at index one. The answer: one and four.
In code, that's one loop and a dictionary. Each lookup takes constant time, so one pass is linear time, and the map can hold every number: linear space.
Don't search for the partner; remember who you've met. That's Two Sum.