Challenge Description: Two Sum II  Input array is sorted
Approach #1: binary search
Note the input array is already sorted. So we can iterate all the elements, for each element(suppose with a value of v1), we try to find another element with the value of targetv1
. Binary search will suitable for this task.
The overall time complexity is $O(NlogN)$.

Approach #2: twoslice
The idea of two slices is similar to binary search. In this approach, we use two index, index l
is from left to right, index r
is from right to left.
In each iteration, we compare the current sum of two elements with the target. There are tree cases:
 sum == target, then we need return current two indexes.
 sum > target, then we need to decrease index
r
.
sum < target, then we need to increase index
l
.The time complexity is $O(N)$.
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0;
int r = numbers.size()1;
while(l < r) {
int s = numbers[l] + numbers[r];
if(s == target) return vector<int> {l+1, r+1};
if(s > target) r;
if(s < target) l++;
}
return vector<int>{};
}
};