Two Sum
Given an array nums and a target, return the indices of the two numbers that add up to target. Exactly one valid answer exists, and you may not reuse the same element twice.
Intuition
We are hunting for a pair that sums to the target. The brute-force instinct is to try every pair, but that repeats a lot of work. The key realization: for any number, its needed partner is fixed — it is target − num. So instead of searching for partners, remember every number already seen and, for each new number, ask “have I already met your partner?”
Any time you're hunting for a pair that satisfies a condition and the brute force is a double loop, ask what the inner loop is actually doing. Here it re-scans for target - n — a pure lookup. Whenever an inner loop is only asking "have I seen this value before?", a hash map deletes it and turns O(n²) into O(n). The same reflex covers two-sum variants, subarray-sum-equals-k, and contains-duplicate.
Approach
Start with brute force — and notice what's wasteful
The most direct idea is: try every pair. For each index i, loop over every later index j and check if nums[i] + nums[j] == target. This is correct and easy to reason about, but it does a lot of repeated work — for each element you re-scan the entire rest of the array, giving O(n²) time. The key observation is that the inner loop is really just asking one question over and over: “is the specific number I need sitting somewhere in the array?” Asking that question by scanning is the slow part.
Turn the search into a lookup
For any number num, the partner that completes the pair is fixed — it must be exactly target − num. So instead of searching for that partner each time, we can remember the numbers we've already walked past in a hash map keyed by value. A hash map answers “have I seen this value, and at what index?” in O(1) on average. That single change replaces the entire inner loop: we no longer look ahead, we look back at what we've recorded.
Walk once, checking before storing
Scan left to right. For the current num, compute need = target − num and ask the map whether need is already there. If it is, we've found the two indices and return immediately. If not, we store num → i and move on. The ordering matters: we check before inserting the current number, which is what lets a value pair with an earlier copy of itself (like the two 3s in [3,3]) without a number ever pairing with itself. One pass, O(n) time.
Solution & live demo
Common pitfalls
Storing the whole array first, then searching
for i, n in enumerate(nums):
seen[n] = i
for i, n in enumerate(nums):
if target - n in seen:
return [i, seen[target - n]]for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = iWith nums = [3, 2, 4] and target = 6, the pre-filled map lets 3 find itself and returns [0, 0]. Checking before inserting means a number can only ever pair with an element that came earlier, so it can never be its own partner.
Keying the map by index instead of value
seen[i] = n ... if target - n in seen: # searching keys that are indices
seen[n] = i ... if target - n in seen: # searching keys that are values
You look things up by value (target - n) and return indices, so value must be the key and index the payload. Reversing them makes every lookup a coincidence of small arrays where indices and values happen to overlap.
Edge cases
We check the map BEFORE inserting the current number, so the first 3 is stored and the second 3 finds it — distinct indices, no reuse.
target − num is plain arithmetic; sign and zero make no difference to the hash lookup.
Overwriting an earlier identical value's index is harmless: any one valid pairing is acceptable and the answer is guaranteed unique.