题目描述

类似于Two Sum，给定一个整型数组，要求返回所有不重复的三元组，且每个三元组的和等于0。

样例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，返回 [ [-1, 0, 1], [-1, -1, 2] ]。

算法0

(暴力枚举，排序去重) $O(n^3 logn)$

时间复杂度分析：$O(n^3 logn)$

C++ 代码

blablabla

算法1

(两重枚举) $O(n^2)$

为了防止放进result有相同答案，每次得到一个答案之后，跳过所有nums[i]的duplicate，并删除hashset中的i。
这样做保证了对每一个st，有且最多只有一个i与之匹配，因为已经sort过，故不会有重复答案出现。

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

C++ 代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        unordered_set<int> hash;
        sort(nums.begin(), nums.end());
        for (int st = 0; st < nums.size(); st++) {
            int n = nums.size();
            while (st > 0 && st < n && nums[st] == nums[st - 1])
                st++;
            hash.clear();
            for (int i = st + 1; i < nums.size(); i++) {
                unordered_set<int>::const_iterator got = hash.find(- nums[st] - nums[i]);
                if (got == hash.end())
                    hash.insert(nums[i]);
                else {
                    res.push_back({nums[st], nums[i], - nums[st] - nums[i]});
                    hash.erase(nums[i]);
                    while(i > 0 && i < n-1 && nums[i+1] == nums[i]) i++;
                }
            }
        }
        return res;
    }
};

算法2

(两重枚举，集合判重) $O(n^2)$

注意循环的时候数组越界

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

C++ 代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        unordered_set<int> hash, vis;
        sort(nums.begin(), nums.end());

        for (int st = 0; st < nums.size(); st++) {
            while (st > 0 && st < nums.size() && nums[st] == nums[st - 1])
                st++;
            hash.clear();
            vis.clear();
            for (int i = st + 1; i < nums.size(); i++) {
                unordered_set<int>::const_iterator got = hash.find(- nums[st] - nums[i]);
                if (got == hash.end())
                    hash.insert(nums[i]);
                else {
                    res.push_back({nums[st], nums[i], - nums[st] - nums[i]});
                    vis.insert(- nums[st] - nums[i]);
                }
                if (vis.find(- nums[st] - nums[i]) != vis.end())
                    hash.erase(- nums[st] - nums[i]);
            }
        }
        return res;
    }
};

算法3

(双指针) $O(n^2)$

注意循环的时候数组越界。
对每一个st，双指针头尾扫。

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

C++ 代码

class Solution {
public:
   vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i=0; i<nums.size(); i++) {
        if ((i>0) && (i<nums.size()) && (nums[i]==nums[i-1]))
            continue;
        int l = i+1, r = nums.size()-1;
        while (l<r) {
            int s = nums[i]+nums[l]+nums[r];
            if (s>0) r--;
            else if (s<0) l++;
            else {
                res.push_back(vector<int> {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--;
            }
        }
    }
    return res;
}
};