Back to Two Pointers
Medium
Two Sum II - Input Array Is Sorted
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` number. Let these two numbers be `numbers[index1]` and `numbers[index2]` where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, added by one as an integer array `[index1, index2]`. You may not use the same element twice and your solution must use only constant extra space.
Examples
Input:numbers = [2,7,11,15], target = 9
Output:[1,2]
The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Constraints
2 <= numbers.length <= 3 * 10^4-1000 <= numbers[i] <= 1000numbers is sorted in non-decreasing order.-1000 <= target <= 1000The tests are generated such that there is exactly one solution.
Approach
Since the array is sorted, we can iterate through the array. For each element `numbers[i]`, we can use binary search on the remaining subarray `numbers[i+1...n]` to find if `target - numbers[i]` exists.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1)
This approach is slower than O(n) but satisfies the O(1) space constraint.
Solution.java
class Solution { public int[] twoSum(int[] numbers, int target) { for (int i = 0; i < numbers.length; i++) { int complement = target - numbers[i]; // Binary search for the complement int left = i + 1; int right = numbers.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (numbers[mid] == complement) { return new int[] { i + 1, mid + 1 }; // 1-based indexing } else if (numbers[mid] < complement) { left = mid + 1; } else { right = mid - 1; } } } return new int[0]; }}