Two Sum
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.
Each input has exactly one solution, and you may not use the same element twice. You can return the two indices in any order.
Example 1
Because nums[0] + nums[1] == 9.
Example 2
The obvious solution checks every pair, which is O(n²). There is an O(n) one — as you walk the array, ask what number you would need to have seen already.
Examples
Example 1
- Input:
- [2,7,11,15], 9
- Output:
- [0,1]
nums[0] + nums[1] = 2 + 7 = 9.
Example 2
- Input:
- [3,2,4], 6
- Output:
- [1,2]
nums[1] + nums[2] = 2 + 4 = 6. Note that nums[0] + nums[0] is not allowed.
Example 3
- Input:
- [3,3], 6
- Output:
- [0,1]
The same value can appear twice, as long as the indices differ.
Constraints
2 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6- Exactly one valid answer exists.
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.