Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return the indices of the two numbers, 1-indexed, as an array of length 2.
Example 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: numbers[0] + numbers[1] = 2 + 7 = 9, returned 1-indexed.
Example 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: numbers[0] + numbers[2] = 2 + 4 = 6.
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers is sorted in non-decreasing orderExactly one valid answer existsThe array being sorted is the whole point — it means you don't need a hash map like unsorted Two Sum.
Start pointers at both ends. What does it tell you if the current sum is too big? Too small?
Because it's sorted, moving the left pointer only ever increases the sum, and moving the right pointer only ever decreases it — that monotonicity is what makes two pointers correct here.
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) return new int[]{left + 1, right + 1};
if (sum < target) left++;
else right--;
}
throw new IllegalArgumentException("No solution");
}Time: O(n) · Space: O(1)