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)

• Thesolutionsetmustnotcontainduplicatetriplets.

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

思路

先对数组进行非递减排序, 确定一个数i，在对其后面的序列使用 左右游标p,q夹逼（PS:这个词确实有点）。  对num[i],num[p],num[q]三者的和sum 进行推断。

假设 sum>target: q--; 去重; 假设 sum<target: p++; 去重; 假设 sum==target: 返回结果; 去重;

这个算法的时间复杂度为O(n^2).

去重技巧:

1. 假设num[i] = num[i - 1]，说明刚才i-1时求的解在这次肯定也会求出一样的，所以直接跳过不求；
2. 事实上指针p不须要从数组头開始，由于假设num[i]所在的解中假设有i之前的数。设其位置为j，那么我们求num[j]时，肯定把num[i]
   也找出来放到和num[j]一起的解里了，所以指针p事实上应该从i+1開始。即初始时p = i + 1, q = num.size() - 1；
3. 当sum == 0，我们保存了当前解以后，须要num[i]在解中的其它的2个数组合，这个时候。肯定是p往后或者q往前。假设++p，发
   现事实上num[p] == num[p-1]，说明这个解肯定和刚才反复了，再继续++p。

   同理，假设–q后发现num[q] == num[q+1]，继续–q。

   这个去重操作主要针对这样的有多个同值的数组，如：-3, 1,1,1, 2,2,3,4。

C++代码

#include 
      
       #include 
       
        using namespace std;class Solution {    public:        vector
        
         
           > threeSum(vector
          
            &num) {            vector
           
            
              > result; if(num.size()<3) return result; sort(num.begin(),num.end()); printf("size: %d\n", num.size()); for (int i=0; i
             
              0){ --q; while(num[q]==num[q+1] &&p
              

newRes; newRes.push_back(num[i]); newRes.push_back(num[p]); newRes.push_back(num[q]); result.push_back(newRes); while(++p

p && num[q]==num[q+1]){ //do nothing } } } } return result; }};int main(int argc, char *argv[]) { int a[] = {-1,0,1}; vector

v(&a[0],&a[3]); Solution s; vector

> result = s.threeSum(v);}

3Sum Closet

再补充其相关题，思路是一样的。直接上代码：

class Solution {public:    int threeSumClosest(vector
      
       & nums, int target) {        int result;        int min_gap = INT_MAX;        sort(nums.begin(), nums.end());        for(int i=0; i