167. Two Sum II - Input Array Is Sorted

發表於 | 分類於

problem

solution

option 1 - Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int l =0, r=n-1;
        while(l<r){
            if(numbers[l] + numbers[r] == target) return {l+1, r+1};
            else if(numbers[l] + numbers[r] < target) l++;
            else r--;
            
        }
        return {-1,-1};
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // use only constant extra space
        vector<int>  ret;
        int n = numbers.size();
        for(int i=0;i<n-1; ++i){
            int l =i+1, r = n-1;
            // Two pointers
            while(l<=r){
                int mid = l+ (r-l)/2;
                if(numbers[i] + numbers[mid] == target) return {i+1, mid+1};
                else if(numbers[i] + numbers[mid] < target)  l= mid+1;
                else r = mid-1;
            }
        }
        return {-1,-1};
    }
};

analysis

  • option 1
    • times complexity O(n)
    • space complexity O(1)
  • option 2
    • times complexity O(nlogn)
    • space complexity O(1)