求数组中和为0的三元组

1. 题目描述

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
注意：
三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。
例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, 0, 10) (-10, -10, 20)

2. 解题思路

找出存在的三元组的和为0。

3. 代码

class Solution {
public:
    vector > threeSum(vector &num) {
        int n = num.size();
        //if(num.empty()) return {};
        //if(n<3) return {{num};
        vector>  result;
        if(num.empty()) return result;
        sort(num.begin(),num.end());
        for(int k=0; k<n; k++){
            if(num[k]>0) break; // 开始遍历元素就大于0 必然不存在和为0的三元组
            int temp = -num[k]; // 遍历后面是否有两个元素相加等于temmp
            int left = k+1,right = n-1;
            while(left<right){
                int sum = num[left]+num[right];
                if(sum==temp){
                   vector  re(3);
                   re[0] = num[k];
                   re[1] = num[left];
                   re[2] = num[right];
                   result.push_back(re);
                   while(left<right&&num[left]==re[1]) left++; // 如果有重复 跳过
                   while(left<right&&num[right]==re[2]) right--;
                }
                else if(sum<temp){
                   left++; //值小了 通过left 增加
                }
                else if(sum>temp){
                   right--;
                }
            }
           while(k+1<n&&num[k]==num[k+1]) ++k;
        }
        return result;
    }
};