Two Sum
You are given an array of integers nums and an integer target. Return the indices of the two distinct elements whose values add up to target. Exactly one such pair exists, and the array is not sorted.
- 2 ≤ n ≤ 10^4
- -10^9 ≤ nums[i], target ≤ 10^9
- Exactly one valid answer exists
- Unsorted array — sorting would lose the indices
- Need to find a *complement*
target - xquickly - One pass with O(1) lookups is the goal
Whenever a brute force re-scans earlier elements to check membership, count, or a complement, a hash table answers the same question in expected O(1) and turns O(n^2) into O(n). Grouping problems reduce to choosing a canonical key (a sorted string, a character-count tuple) and bucketing by it.
Scan the array once while maintaining a hash map from value to index. For each element x, check whether target - x is already in the map; if so, the stored index and the current index are the answer. Otherwise insert x. Checking before inserting guarantees the two indices are distinct.
- Sort a copy with original indices attached and use opposite-direction two pointers in O(n log n) time and O(n) extra space — this is what you use when the array is already sorted (see Two Sum II).