Two Sum II 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 t
. Let
these two numbers be numbers[index1]
and numbers[index2]
where 1 <= index1 < index2 <= numbers.length
.
Return the indices of the two numbers, index1
and index2
, added by one as an integer array [index1, index2]
of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example
- Input:
numbers = [2,7,11,15]
, target = 9 - Output: [1,2]
- Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Solution (Java)
So Two Sum problem is a very famous problem. Genereally, you encounter the unsorted version, where the Hashmap solves it in O(n)
.
This problem is a bit different because it says you’re not allowed to use extra space, i.e., only use O(1)
memory. This means
the hashmap is out of the question.
This gives also the hint to use pointers. Moreover, in order to solve it in O(n)
and reduce the search space, we can start with
setting one pointer to i=0
and one to j=n-1
(the end of array) and narrow it down to the center.
Since the array is sorted, if we move i
to the right, we know that the two-sum gets larger. If we move j
to the left, we know that the sum gets smaller.
Using these two properties, we can compare the current sum to target t
and move the pointers until it equals t
.
class Solution {
public int[] twoSum(int[] numbers, int target) {
// note that we are not allowed to use additional space!
int ptrL = 0;
int ptrR = numbers.length - 1;
int[] arr = new int[2];
while(ptrL != ptrR){
if(numbers[ptrL] + numbers[ptrR] == target){
arr[0] = ptrL+1; arr[1] = ptrR+1;
return arr;
}
else if(numbers[ptrL] + numbers[ptrR] > target){
ptrR--;
}
else{
ptrL++;
}
}
return arr;
}
}