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

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        int len = num.size();
        if(len < 3)    return {};

        vector<vector<int>> res;
        sort(num.begin(), num.end());
        for(int i=0; i<len-2; i++) {
            // 对 i去重，有重复的话，只输出一次
            while(i>0 && num[i]==num[i-1])
                i++;
            int left = i+1;
            int right = len-1;
            while(left < right) {
                if(num[i]+num[left]+num[right] == 0) {
                    res.push_back({num[i], num[left], num[right]});
                    // 对 left和 right去重。
                    while(right<len && num[right]==num[right-1])    right--;
                    while(left>i && num[left]==num[left+1])    left++;
                    // 更新 left和 right
                    left++;
                    right--;
                } else if(num[i]+num[left]+num[right] < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }
};