Two Sum II - Input Array Is Sorted
medium
two-pointers
arrays
binary-search
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two distinct numbers that add up to a specific target.
Return the positions of the two numbers, index1 and index2, added by one (so they are 1-based), as an array [index1, index2] with index1 < index2.
The tests are generated so that there is exactly one solution, and you may not use the same element twice.
Input / output
- Input:
numbers: int[](sorted, 1-indexed),target: int - Output:
int[]of length 2 — the two 1-based positions, smaller first
Constraints
2 <= numbers.length <= 30000-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order.-2000 <= target <= 2000- Exactly one valid answer exists.
Follow-up
Can you solve it using only O(1) extra space? The sorted order is the key that lets you avoid the hash map needed for the unsorted Two Sum.
Examples
Example 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Example 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Example 3
Input: numbers = [-1,0], target = -1
Output: [1,2]
