相向双指针

167. 两数之和Ⅱ-输入有序数组

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

15.三数之和

本题可以看作两数之和的升级版，即固定一个数不动，看另外两个数之和是否等于这个数的相反数。时间复杂度为 \(O(n^2).\) （枚举第一个数为 \(O(n)\)，双指针为 \(O(n)\)）。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());//先排序，方便尺取
        vector<vector<int>> ans;
        int n = nums.size();
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i && x == nums[i - 1]) continue;//跳过重复数字（当前nums[i]已经被使用过）
            if (x + nums[i + 1] + nums[i + 2] > 0) break;//当x与其后的两个数之和大于0，说明这组无解（后面的数变大或x变大都不可能再等于0）
            if (x + nums[n - 2] + nums[n - 1] < 0) continue;//如果x与最后面的两个数之和小于0，说明后面两个数变小也仍然小于0，只有增大x。
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = x + nums[l] + nums[r];
                if (sum > 0) r--;
                else if (sum < 0) l++;//尺取
                else {
                    ans.push_back({x, nums[l], nums[r]});
                    l++;//当前的l和r所指向的数下回不能再使用。
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    r--;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                }
            }
        }
        return ans;
    }
};