解题思路

双指针

虽然这是三个数的，但也可以用双指针

1. 先将数组排序
2. 我们把一个数不动，这个数后面的第一个数为 l 指针，nums.size() - 1 为 r 指针，每次计算三数之和，若大于 0 则移动 r ，否则移动 l
3. 判重：在找到为 0 的方案时，判断后一个数是否与前一个数相等，若相等移动指针,定的数同理
4. 若定的数遍历到大于 0 了，那么一定不会出现满足要求的方案了，因为数组已经排好序。

时间复杂度：O(n^2)

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if (n < 3) return res;//若数组长度大于3则直接返回

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n; i ++)//外层循环定的数
        {
            if (nums[i] > 0) break;//若遍历到大于0则直接返回，一定不会出现满足条件的数
            if (i && nums[i] == nums[i - 1]) continue;//判重

            int l = i + 1, r = n - 1;
            while (l < r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                if (!sum)
                {
                     res.push_back({nums[i], nums[l], nums[r]});
                    //判重
                    while (l < r && nums[l] == nums[l + 1]) l ++;
                    while (l < r && nums[r] == nums[r - 1]) r --;

                    l ++;
                    r --;
                }
                else if (sum > 0) r --;//若大于0移动r
                else l ++;//否则移动l
             }
        }
        return res;
    }
};