The problem
You are given an array of integers nums and a number target. Exactly two of the numbers, at different positions, add up to target.
Return the positions (indices) of those two numbers, in any order. The same element cannot be used twice, and there is always exactly one answer.
Examples
- Input
nums = [2, 7, 11, 15], target = 9
- Output
[0, 1]
- Input
nums = [3, 2, 4], target = 6
- Output
[1, 2]
- Input
nums = [3, 3], target = 6
- Output
[0, 1]
Constraints
- 2 ≤ nums.length ≤ 10⁴
- −10⁹ ≤ nums[i], target ≤ 10⁹
- Exactly one valid answer exists.
The idea
Checking every pair works, but that is n × n comparisons. Turn the question around: standing on a number x, the partner it needs is target − x. So the only question is “have I already seen target − x?”
A hash map (a table that finds a value by its key in constant time on average) remembers each number’s index as we walk past it. For each x: if target − x is in the map, we have the pair; otherwise store x and move on. One pass, and each lookup is one step.
- Time
- O(n) — one pass, constant-time lookups
- Space
- O(n) — the map holds up to n numbers
Solution · every language run against every case
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: seen = {} # value -> index where we saw it for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return []