LeetCode----3 Sum

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)

  分析：

  这道题原本不难，但是题目要求结果不能够包含重复的 triplets, 往往容易出错。

  思路1：

  step 1： 先排序

  step 2: 枚举前两个数，如果要满足 sum = 0, 那么第三个数必须是 前两个数和的负数。

  通过二分搜索去查找。。复杂度 是 O(N^2 * lgN)

  
  

  思路2：

  O（N^2)的算法。

  借助于 2 sum的思路：如果在一个已经排序的数组中，寻找两个数的和为给定的sum, 其实有 O（N）的算法。

  指针 i, j 分别指向数组的首尾，如果 num[i] + num[j] < 0, 则 i++; 如果 > 0, j--; 直到和等于sum.

  因此，本题可以

  step 1: 排序

  step 2: 先枚举第一个数，然后在排好序的数组中寻找 两个数和等于 第一个数的负数。

  Note: 为了避免重复的 triplets, 有一些小细节需要考虑。具体见下面的代码。

  基本的思想就是 如果碰到相邻的数相同，可以跳过。

  
  

  class Solution {
  public:
      vector
      
        > threeSum(vector
       
         &num) { vector
        
          > result; if(num.size() < 3) return result; sort(num.begin(), num.end()); //处理以num[k]开头的和 for(int k=0; k
         
           0 && num[k] == num[k-1]) continue; //避免重复 int i=k+1, j=num.size()-1; //分别指向首尾 while(i < j){ if(i > k+1 && num[i] == num[i-1]){ ++i; continue; } if(j < num.size()-1 && num[j] == num[j+1]){ --j; continue; } if(num[k] + num[i] + num[j] < 0) ++i; else if(num[k] + num[i] + num[j] > 0) --j; else{ result.push_back(vector
          
           {num[k], num[i++], num[j--]}); } } } return result; } };