LeetCode之3Sum

【题目】

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)
  

  Discuss

  
  

  【题意】

  给定n个整数的数组S，是否在 数组S中有元素a，b，C，使得A + B + C =0？在数组中找出独一无二的三元素组，使得他们之和为0。
  

  注意：

  在三元素组（A，B，C）中，必须满足非递减排序。 （即A≤B≤C）

  该解决方案集中一定不能包含重复的三元素组。

  【分析】

  先排序，然后二分查找，复杂度 O(n^2*log n)。a + b + c = 0 即 b + c = -a

  题目思路与 剑指Offer之和为S的连续正数序列 博文思路一致。可以参考一下解题思路。
  

  另有：点击打开链接 详细总结

  【代码】

  /*********************************
  *   日期：2014-01-18
  *   作者：SJF0115
  *   题号: 3Sum
  *   来源：http://oj.leetcode.com/problems/3sum/
  *   结果：AC
  *   来源：LeetCode
  *   总结：
  **********************************/
  #include 
      
       
  #include 
       
         #include 
        
          #include 
         
           using namespace std; class Solution { public: vector
          
            > threeSum(vector
           
             &num) { int i,j,target,start,end; int Len = num.size(); vector
            
              triplet; vector
             
              > triplets; //排序 sort(num.begin(),num.end()); for(i = 0;i < Len-2;i++){ //跳过重复元素 if(i != 0 && num[i] == num[i-1]){ continue; } //a + b + c = 0 target = -num[i]; //二分查找 start = i + 1; end = Len - 1; while(start < end){ int curSum = num[start] + num[end]; //相等 -> 目标 if(target == curSum){ triplet.clear(); triplet.push_back(num[i]); triplet.push_back(num[start]); triplet.push_back(num[end]); triplets.push_back(triplet); //注意： 跳过重复元素 while(start < end && num[start] == num[start + 1]){ start ++; } while(start < end && num[end] == num[end - 1]){ end --; } start ++; end --; } //大于 -> 当前值小需要增大 else if(target > curSum){ //注意：跳过重复元素 while(start < end && num[start] == num[start + 1]){ start ++; } start ++; } //小于 -> 当前值大需要减小 else{ //注意：跳过重复元素 while(start < end && num[end] == num[end - 1]){ end --; } end --; } }//while }//for return triplets; } }; int main() { vector
              
               > result; Solution solution; vector
               
                 vec; vec.push_back(-2); vec.push_back(0); vec.push_back(0); vec.push_back(2); vec.push_back(2); result = solution.threeSum(vec); for(int i = 0;i < result.size();i++){ for(int j = 0;j < result[i].size();j++){ printf("%d ",result[i][j]); } printf("\n"); } return 0; } 
               
              
             
            
           
          
         
        
       
      

  
  
  

  【测试】

  Input:	[-2,0,0,2,2]
  Expected:	[[-2,0,2]]