给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。

注意事项

在三元组(a, b, c)，要求a <= b <= c。

结果不能包含重复的三元组。

样例

如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：
(-1, 0, 1),(-1, -1, 2)

双指针加set暴力去重

三数之和相比于两数之和要稍微复杂一些，如果不加任何思考直接遍历所有可能的组合，这当然是一种方法，但是时间复杂度可能就会变得不能接受，所以一种比较好的方法是排序之后采用双指针的方法。具体算法如下：

1. 排序。排序可以让数据变得有序，在许多算法中都有使用。
2. 定义三个指针i,left,right.
3. i用来遍历数据，从下下标为0一直到sz-3。
4. 对于每一个i，令left=i+1，right=sz-1，然后检查三个指针所指数据的和，
   如果为0，说明找到一个符合条件的组合，把三个数放入vector中然后再放入set中，接着把left++,right--。
   如果>0,则说明当前的right偏大，则把right--,因为是排序的，所以整体和会变小。
   如果<0,说明当前的left偏小，则把left++,因为是排序的，所以整体的和会变大。（这里变大变小不是一定的，因为可能存在重复的数据，不影响）
   这里主要要理解的是如果为0的话为什么left和right同时可以变化，这是因为要求去重，如果只改变一个还符合条件的话一定是重复的，即使两个都改变还是可能会出现重复的组合，所以放在set中进行暴力去重。还有一种写法不用set去重，增加了去重的判断条件，我认为这种写法增加了算法的复杂度，所以没有用。有兴趣可以看这里.

这样对于每个i来说，只遍历其后的数据，而且利用双指针有效避免了一些重复搜索。代码写起来也比较简洁：

 vector<vector<int>> threeSum(vector<int> &numbers) {
        set<vector<int>> sres;
        vector<vector<int>> res;
        int sz=numbers.size();
        if(sz<3)  return res;
        sort(numbers.begin(),numbers.end());      //先排序
        vector<int> tmp;
        
        for(int i=0;i<=sz-3;i++)
        {
            int left=i+1;
            int right=sz-1;
            while(left<right)
            {
                
                if(numbers[i]+numbers[left]+numbers[right]==0)   //符合条件
                {
                    tmp.push_back(numbers[i]);
                    tmp.push_back(numbers[left]);
                    tmp.push_back(numbers[right]);           //放入vector
                    sres.insert(tmp);                     //插入set，去重
                    tmp.clear();                //清空tmp
                    left++;
                    right--;                 //这两个指针都移动，因为原题是要求去重的，如果只移动一个还满足的话肯定是重复的。
                }
                else if(numbers[i]+numbers[left]+numbers[right]<0)
                {
                    left++;             //如果小，就把左边的指针右移
                }
                else 
                right--;               //大的话，就把右边的指针左移
            }
            
        }
        for(auto s:sres)              //去重之后的结果放入vector
        {
            res.push_back(s);
        }
        
        return res;
        
        // write your code here
    }

---

顺便复习一下set，刚才写的时候竟然用了push()，一段时间不写果然是忘记很快。
set的资料见set
列出一些基本的成员函数以供参考，掌握一些常用的就可以了：

set