Two Sum
EasyArrays and hashing
You are given an array of integers nums and an integer target. Exactly one pair of numbers in nums adds up to target.
Return the indexes of those two numbers, in either order. The two indexes must be different, though the numbers at them can be equal.
Examples
Input: nums = [4, 9, 1, 6], target = 7 Output: [2, 3]
nums[2] + nums[3] is 1 + 6 = 7.
Input: nums = [5, 5, 11], target = 10 Output: [0, 1]
The same value, at two different indexes.
Constraints
2 ≤ nums.length ≤ 10⁴-10⁹ ≤ nums[i], target ≤ 10⁹- Exactly one pair works.
Stuck?
Hint 1
For each number, the partner you need is target - number. How quickly can you tell whether you have already passed it?
Hint 2
Keep a Map from each value to its index as you go. One pass is enough.
The idea
Every number has exactly one partner that completes the pair: target minus itself. Go through the array once, keeping a Map from each number you have passed to its index. As soon as the current number's partner is in the Map, you have the pair.
Time O(n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
indexOf maps each number already passed to its index. Looking a number up in a Map takes constant time, and that is what replaces a second loop.
function twoSum(nums, target) { const indexOf = new Map(); for (let i = 0; i < nums.length; i++) { const partner = target - nums[i]; if (indexOf.has(partner)) return [indexOf.get(partner), i]; indexOf.set(nums[i], i); } return [];}The trap
Two loops that both start at 0 compare each number with itself as well. When a number is exactly half of target, it pairs with itself and the answer repeats one index. The inner loop has to start after i, and even then two loops take O(n²) time.
function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) for (let j = 0; j < nums.length; j++) if (nums[i] + nums[j] === target) return [i, j]; // j can equal i}