You are given a list of integers nums and an integer target. Exactly two different
positions in nums hold numbers that add up to target.
Return those two positions (indices, counting from 0) as a list of two numbers, in either order. You may not use the same position twice, although two positions may hold equal numbers.
Example 1
- Input
- nums = [3, 9, 14, 5], target = 8
- Output
- [0, 3]
nums[0] + nums[3] is 3 + 5 = 8.Example 2
- Input
- nums = [6, 2, 6], target = 12
- Output
- [0, 2]
Constraints
numsholds 2 to 10⁴ numbers.- Every number, and
target, is between −10⁹ and 10⁹. - At least one pair adds up to
target; if several do, any one of them is accepted.
Show the pattern
Hashing
For each number you need to know, instantly, whether its partner (target minus it) has already appeared. That is a lookup, and a hash map answers lookups in constant time.
See hashing in a visualiserShow the approach
Walk through the list once, keeping a hash map from each number seen so far to its position.
For the number x at position i, its partner is target - x. If the partner is already in the
map, return its position with i. Otherwise record x → i and move on.
Checking for the partner before recording x is what stops a number pairing with itself.
Time: O(n) · Space: O(n)