题解 | #三数之和#

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // 找出 a + b + c = 0
        // a = num[i], b = num[left], c = num[right]
        sort(num.begin(), num.end());   // 先对num数组进行升序排序
        vector<vector<int>> res;
        for(int i = 0; i < num.size(); ++i){
            if(num[0] > 0) return res;  // 如果排序之后的第一个元素都>0，则没有符合要求的三元组，直接返回res
            // 对a去重
            if(i > 0 && num[i] == num[i - 1]) continue;
            int left = i + 1, right = num.size() - 1;
            while(left < right){
                if(num[i] + num[left] + num[right] > 0){    // 三数之和大于0，说明right对应的数太大了，right左移
                    --right;
                } else if(num[left] + num[i] + num[right] < 0){ // 三数之和小于0，说明left对应的数太小了，left右移
                    ++left;
                }else{
                    res.push_back({num[i], num[left], num[right]});
                    // 对b，c元素去重，要在找到第一个三元组之后
                    while(left < right && num[right] == num[right - 1]) --right;
                    while(left < right && num[left] == num[left + 1]) ++left;

                    // 以上两个while找到两端相同的元素，要再同时收缩一个
                    --right;    
                    ++left;
                }
            }
        }
        return res;
    }
};