Two Sum — hash map in one pass

Intuition#

Instead of checking every pair (O(n²)), remember what we’ve seen. For each number x, the complement we need is target - x. If we already saw it, we’re done.

Go#

1
func twoSum(nums []int, target int) []int {
2
    seen := make(map[int]int, len(nums))
3
    for i, x := range nums {
4
        if j, ok := seen[target-x]; ok {
5
            return []int{j, i}
6
        }
7
        seen[x] = i
8
    }
9
    return nil
10
}

Trap#

• Don’t put seen[x] = i before the lookup. You’d match x + x = target against itself with the same index.
• Guaranteed exactly one solution — so no “best pair” logic needed.

Complexity#

• Time: O(n) — one pass, map ops are amortized O(1)
• Space: O(n) — worst case we store every element