题目:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique 

triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},    A solution set is:    (-1, 0, 1)    (-1, -1, 2)

解题思路:

    在上一篇博客里面，简述了Two Sum的做法，而这道题目与其类似，我们可以通过把等式 a + b + c = 0 转换

成求 -b = a + c ,关于这里为什么是选择b做和？因为我们最终所要求的三元组里面是非降序的，而选择b做和的

一个好处就是我们只用去枚举b的位置.假设数组长度为n,则b的可能位置为[1,n-2].这题目里面个人感觉主要是怎

么去重的问题,下面阐释下我的做法:当枚举b时，由于我们设定头尾遍历法求解，那么满足条件<a,b,c>的三元组且

重复的必然相邻(因为b此时是定值),所以我们需要记录上一次找到的满足条件的三元组，然后做个比较即可去重.

这里还存在一个优化:现假设我们枚举b的位置为k，如果k - 1的位置的数值也等于b，则满足等式a + b + c = 0 

且<a!=b,b,c>的结果集我们已经在k - 1时已经得知，所以我们这里只需要去找寻有没有满足<b,b,c>这样的等式即

可.最终所要找寻到的结果集就是无重复的结果集.

下面是解题代码:

class Solution {public:    vector<vector<int> > threeSum(vector<int> &num)     {        sort(num.begin(),num.end());        int n = num.size();        vector<vector<int> > res;        int arr[3] = {-1,-1,-1};        for(int k = 1 ; k < n - 1 ;++k)        {            if(k > 1 && num[k] == num[k-1])            {                long long key = -num[k] * 2 ;                if(num[k-1] != num[k-2] && binary_search(num.begin()+k+1,num.end(),key))                {                    arr[0] = num[k] , arr[1] = num[k] , arr[2] = key;                    res.push_back(vector<int>(arr,arr+3));                }                continue;            }            int sum = -num[k],i=0,j=n-1;            while(i < k && j > k)            {                long long tmp = num[i] + num[j] ;                if(tmp == sum)                {                    if(num[i]!=arr[0] || num[k]!=arr[1] || num[j]!=arr[2])                    {                            arr[0] = num[i] , arr[1] = num[k] , arr[2] = num[j];                        res.push_back(vector<int>(arr,arr+3));                    }                    ++i,--j;                    continue;                }                tmp > sum ? --j : ++i ;            }        }        return res;    }};