167. 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, 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.

• binary search solution
• Time : O(nlogn)
• Space : O(1)

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int>::iterator it = numbers.end();
        for(int i = 0; i < numbers.size(); i++) {
            it = lower_bound(numbers.begin() + i + 1, it, target - numbers[i]);
            if(it != numbers.end() and *it + numbers[i] == target) {
                return {i+1, (int)(it - numbers.begin())+1};
            }
        }
        return {};
    }
};

• two pointer solution
• Time : O(n)
• Space : O(1)

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