167. Two Sum II — Input array is sorted

這用two sum的方法一樣解的出來, 但這題有binarysearch, 還是會練習一下怎麼使用

先附上用two sum的解法

class Solution {
  public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        int size = numbers.size();
        std::unordered_map<int, int> table;
        for (int i = 0; i < numbers.size(); i++) {
            int cur = target - numbers[i];
            if (table.count(cur)) {
                return std::vector<int>{table[cur] + 1, i + 1 };
            } else {
                table[numbers[i]] = i;
            }
        }
        return std::vector<int>{};
    }
};

但二分搜尋法的方式時間複雜度是O(nlogn), 並沒有比較快, 倒是看到two_pointer的解法

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