Problem
Given a 1-indexed integer array numbers that is sorted in non-decreasing order and an integer target, find two numbers such that their sum equals target.Return the indices of the two numbers as an array [index1, index2], where 1 <= index1 < index2 <= numbers.length. Each input has exactly one solution, and the same element cannot be used twice.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
numbers = [2,7,11,15]
target = 9 Output
[1,2]Solution
This solution uses the Two Pointer technique. One pointer starts at the beginning of the array, while the other starts at the end.The sum of the two values is compared with the target. If the sum is smaller than the target, the left pointer is moved forward to increase the sum. If the sum is greater than the target, the right pointer is moved backward to decrease the sum.
Since the array is sorted, each pointer movement eliminates a range of impossible pairs. When the sum equals the target, the two 1-based indices are returned immediately.
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int 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--;
}
}
return new int[] {};
}
Complexity
The two pointers move toward each other, and each element is processed at most once. Therefore, the overall time complexity isO(n).
The algorithm uses only two pointers and a few variables, resulting in an extra space complexity of
O(1).