Maintained by Vikas Dulgunde, software engineer
You are given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target.
You can assume each input has exactly one solution, and you may not use the same element twice. Return the two indices in ascending order.
This is the canonical warm-up for the hash-map pattern, and how you solve it says a lot. The naive answer is a double loop; the answer interviewers want trades a little memory for a single pass.
nums[0] + nums[1] = 2 + 7 = 9, so the answer is the pair of indices 0 and 1.
nums[1] + nums[2] = 2 + 4 = 6. The leading 3 is a distractor; doubling it would need a second 3, which is not present.
Two equal values at different indices are a valid pair. This is the case that breaks a careless solution which lets one element match itself.
Visible test cases
A double loop that checks every pair works but is O(n^2). What would let you find the partner of a number without scanning the rest of the array each time?
As you walk the array you always know what you still need: target minus the current value. Could you remember the numbers you have already passed?
Keep a hash map from value to index. Before storing the current number, check whether its complement is already in the map. Checking before inserting is what stops a number from pairing with itself.
Try every pair of indices and check whether they sum to the target. Correct and easy to reason about, but quadratic, which is too slow once the array is large. Use it only to state a baseline out loud before improving it.
Trade memory for time. Walk the array once, keeping a map from each value to the index where you saw it. For the current number compute its complement, target minus the number; if the complement is already in the map you have found the pair. Otherwise record the current number and move on. Because you check before you insert, a value can never pair with itself.