LeetCode:3Sum

题目:

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时，由于我们设定头尾遍历法求解，那么满足条件
   
    的三元组且
   

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

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

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

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

下面是解题代码:

class Solution 
{
public:
    vector
    
      > threeSum(vector
     
       &num) { sort(num.begin(),num.end()); int n = num.size(); vector
      
        > 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
       
        (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
        
         (arr,arr+3)); } ++i,--j; continue; } tmp > sum   --j : ++i ; } } return res; } };