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 target-v1. Binary search will suitable for this task.

The overall time complexity is $O(NlogN)$.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i=0 ;i < numbers.size() - 1; i++) { 
            int l = i + 1; 
            int r = numbers.size()  - 1;
            int t = target - numbers[i];
            while(l <= r) { 
                int m = (l + r) / 2;
                if(numbers[m] == t) { 
                    return vector<int> { i+1, m+1 };
                } else if (numbers[m] > t) { 
                    r = m - 1;
                } else  {
                    l = m + 1;
                }
            }
        }
        return vector<int>{};
    }
};

Approach #2: two-slice

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>{}; } };