LC167. 两数之和 II - 输入有序数组

题目链接：167. 两数之和 II - 输入有序数组

题解

• 数组已经排好序，对于 $numbers[i]$ 只需要用二分搜索查找 numbers 中有没有满足 $target - numbers[i]$。

• 另外也可以用双指针来做，复杂度可以降到 $O(n)$

参考代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int>ans;
        for (int i=0;i<numbers.size();i++) {
            int need = target - numbers[i];
            int k = lower_bound(numbers.begin()+i+1, numbers.end(), need) - numbers.begin();
            // cout<<need<<" "<<k<<" "<<i<<endl;
            if (k >= numbers.size()) {
                continue;
            }
            if (numbers[i] + numbers[k] == target) {
                ans.push_back(i+1);
                ans.push_back(k+1);
                break;
            }
        }
        return ans;
    }
};