题解 | #数组中相加和为0的三元组#

利用单调性即可，去重可以考虑将三元组映射成一个整数。

时间复杂度：
空间复杂度：

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        unordered_map<int,bool> hash;
        vector<vector<int>> res;
        for(int i=0;i<n-2;i++) {
            int k = n - 1;
            for(int j=i+1;j<n-1;j++) {
                int s = nums[i] + nums[j];
                while(k > j && s + nums[k] > 0) k--;
                if(k > j && s + nums[k] == 0) {
                    int val = nums[k];
                    if(!hash.count(n * nums[i] + 19937 * nums[j] + nums[k])) 
                        res.push_back({nums[i], nums[j], nums[k]});
                    hash[n * nums[i] + 19937 * nums[j] + nums[k]] = 1;
                    while(k > j && nums[k] == val) k--;
                }
            }
        }
        return res;
    }
};