Two Sum II - Input Array Is Sorted
MediumTwo Pointers
You are given an integer array numbers sorted in non-decreasing order, and an integer target. Find two different positions whose values add up to target.
Return [index1, index2] using 1-based indices, with index1 < index2. The input always has exactly one such pair. Two positions may hold the same value, but you cannot use one position twice.
Aim for O(1) extra space.
Example 1
- Input:
- numbers = [1,3,4,8], target = 7
- Output:
- [2,3]
- Explanation
- 3 and 4 sum to 7. They sit at indices 2 and 3 once counting from one rather than zero.
Example 2
- Input:
- numbers = [-5,-2,0,9], target = 4
- Output:
- [1,4]
- Explanation
- The pair is the smallest and largest values, -5 and 9, at the two ends.
Example 3
- Input:
- numbers = [2,3,3,5], target = 6
- Output:
- [2,3]
- Explanation
- The two 3 values are separate elements, so using both is valid and gives the pair at indices 2 and 3.
Constraints
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order-1000 <= target <= 1000- Exactly one valid pair exists