三数之和

力扣 15

给你一个长度为 \(n\) 的序列，请你寻找出所有的子序列 nums[i], nums[j], nums[k] 使得 nums[i] + nums[j] + nums[k] = 0 并要求 i、j、k 两两互不相同。

输出的结果不能包含重复的子序列。

输入样例

nums = [-1,0,1,2,-1,-4]

输出样例

res = [[-1,-1,2],[-1,0,1]]

完善代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

    }
};

排序 + 双指针

先将数组排序，然后从起点 i = 0 处一直往后面遍历，直到 i == n || nums[i] > 0 时停止；

定义左右指针 l = i + 1, r = n - 1，这样就形成了 nums[i] <= nums[l] <= nums[r] 并且还保证了最小的 nums[i] <= 0

如果 nums[i] + nums[l] + nums[r] < 0 说明 nums[l] 小了，l 要右移一个单位；如果 nums[i] + nums[l] + nums[r] > 0 说明 nums[r] 大了，r 要左移一个单位；如果 nums[i] + nums[l] + nums[r] == 0，就讲 {nums[i], nums[l], nums[r]} 丢入元组 set<vector<int>> st 中，这样的好处是可以对结果去重。

排序 + 双指针代码参考

class Solution {
public:
    vector<vector<int>> res;
    set<vector<int>> st;
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3) return res;
        int n = nums.size();
        sort(nums.begin(), nums.end(), [](int a, int b)->bool{return a < b;});
        for (int i = 0; i < n; i ++)
        {
            int l = i + 1, r = n - 1;
            while (l < r)
            {
                int t = nums[i] + nums[l] + nums[r];
                if (t == 0) st.insert({nums[i], nums[l], nums[r]}), l ++, r --;
                else if (t < 0) l ++;
                else r --;
            }
        }
        for (auto x : st) res.push_back(x);
        return res;
    }
};