Two Sum
You get a list of whole numbers and a goal value. Exactly two numbers in the list add up to the goal, and your job is to report where they sit.
Take nums = [3, 8, 12, 5] and target = 17. The value 12 is at index 2 and 5 is at index 3, and 12 + 5 = 17, so the answer is [2, 3].
The two numbers must come from two different positions. In [4, 2, 6] with target = 8, using the 4 twice is not allowed; the answer is [1, 2] because 2 + 6 = 8. The same value may appear twice, though: in [7, 3, 7] with target = 14 the answer is [0, 2].
Write a function named twoSum that gets an array of integers nums and an integer target, and returns an array of two indices [i, j] such that nums[i] + nums[j] equals target.
The indices must be two different positions, returned in increasing order (i smaller than j). Every input has exactly one such pair.
Constraints: 2 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9, -10^9 ≤ target ≤ 10^9.
Function
- arg1integer-array
- arg2integer
- Returnsinteger-array
Examples
- Input
- arg1 = [3, 8, 12, 5]arg2 = 17
- Output
- [2, 3]
- Input
- arg1 = [6, 1, 4, 10]arg2 = 7
- Output
- [0, 1]
- Input
- arg1 = [2, -6, 9, 4, 13]arg2 = 3
- Output
- [1, 2]
+13 hidden tests on Submit
Hints
Open them one at a time. Each one gives away a little more.
Trying every pair with two nested loops is correct, but on 10,000 numbers that is about 50 million checks. Can you find each number's partner without scanning the list again?
When you stand on a value
x, you already know which value would complete the pair: the target minusx. The only question is whether you have passed that value before, and at which index.Walk the list once and keep a hash map from each value you have passed to its index. At every position, look up the missing partner first; if it is in the map, you have both indices. Otherwise store the current value and move on. Looking up before storing is what stops a number from pairing with itself.
A full walkthrough of this problem is on its way.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def twoSum(nums, target):
# Write code hereCase 1
Case 2
Case 3
Input
arg1 = [3, 8, 12, 5] arg2 = 17
Expected
[2, 3]