三数之和【双指针】

1.先来看前面的三道双指针题目

发现：都是一个类型！

2.照葫芦画瓢

1. 递增排序
2. 固定⼀个数X
3. 在这个数后面的区间，找到两个数的和是X的相反数

去重

代码

#include <vector>
class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ret;
        int cur = 0, n = nums.size();
        while (cur < n)
        {
            // 在递增数组中 当前的数大于0 那么该数之后的数均大于0
            // 则nums[i]后无法找到两个数的和==该数的相反数
            if (nums[cur] > 0)
                break;

            int left = cur + 1, right = n - 1, target = -nums[cur];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target)
                    right--;
                else if (sum < target)
                    left++;
                else
                {
                    ret.push_back({nums[cur], nums[left++], nums[right--]});

                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }
            cur++;
            while (cur < n && nums[cur] == nums[cur - 1])
                cur++;
        }
        return ret;
    }
};