Two Sum
Problem
Given an array of integers and a target, return the indices of the two elements that add up to the target. Exactly one valid pair exists, and an element cannot be paired with itself.
Examples
Constraints
- • 2 <= nums.length <= 10^4
- • -10^9 <= nums[i], target <= 10^9
- • Exactly one answer exists
Hints & approach
Hint 1
For each number x, what other number are you looking for?
Hint 2
Checking all pairs is O(n^2). Can you look up the complement faster?
Hint 3
Store each value's index in a map as you scan, and check for target - x before inserting x.
Approachtry the hints first
Scan the array once while maintaining a map from value to index. For each element x at index i, compute need = target - x; if need is already in the map, return [map[need], i]. Otherwise insert x -> i and continue. Checking before inserting guarantees an element is never paired with itself, and duplicates like [4,4] work naturally.
Time O(n) · Space O(n)