BeginnerArrays & Strings
Two Sum: look up the partner, don't search for it
For each number x, the partner you need is target − x. Store what you've passed in a map and look the partner up in O(1).
The idea
The brute force tries every pair. The insight: once you fix x, you know exactly which number completes it, target − x. So the question becomes “have I already seen target − x?”, which a hash map answers instantly.
Store value → index as you go, so when you find the partner you can return both positions.
Worked example
nums = [2, 7, 11, 15], target = 9
- i=0, x=2: need 7, not seen. Store {2: 0}.
- i=1, x=7: need 2, seen at index 0 → answer [0, 1].
In code (Python)
def two_sum(nums, target):
index_of = {}
for i, x in enumerate(nums):
need = target - x
if need in index_of:
return [index_of[need], i]
index_of[x] = iO(n) time, O(n) space.
How to spot it
- “two numbers that add up to”, “pair with difference k”, “complement”.
Common mistakes
- Storing x before checking, which pairs a number with itself (target 6, x = 3).
- Returning values when the question asks for indices.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →