Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+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)

  Subscribeto see which companies asked this question

  Show Tags

  Show Similar Problems

  
  

  题目的大概意思是：给定一组整数，找出所有能使和为0的三个数，且不重复。

  这道题难度等级：中等

  思路：

  1、与题目Two Sum类似，先将数组nums进行排序，然后从左往右依次枚举，在枚举的过程中左右夹逼；

  2、枚举位置为i，当nums[i]为正数时，结束枚举（因为不可能三个正数之和为0）；另外，要枚举过整数不再重复枚举；

  3、枚举到i时，左、右位置分别用l、r表示，当nums[i]+nums[l]+nums[r]>0，右边界往左夹逼；当nums[i]+nums[l]+nums[r]<0，左边界往右夹逼；当nums[i]+nums[l]+nums[r]==0，则算找到一个，要存起来，再将左边界往右夹逼同时要跳过与之前左边界相同的值，否则会出现重复的三个数。

  4、在步骤3的整个过程中，始终要保证l 。

  代码如下：

  class Solution {public:    vector
                      
                       
                        > threeSum(vector
                        
                         & nums) { vector
                         
                           > res; sort(nums.begin(), nums.end()); vector
                          
                            tmp(3,0); int l, r; for (int i = 0; i < nums.size() && nums[i] <= 0; ++i){//从左往右枚举 if (nums[i] != nums[i - 1] || i == 0){ l = i + 1; r = nums.size() - 1; while(l < r ){ while (l < r && nums[i] + nums[l] + nums[r] > 0){--r;}//限制右边界 if (l < r && nums[i] + nums[l] + nums[r] == 0){ tmp[0] = nums[i]; tmp[1] = nums[l]; tmp[2] = nums[r]; res.push_back(tmp); while(l < r && nums[l] == tmp[1]){++l;}//限制左边界 } else{ ++l; } } } } return res; }};
                          
                         
                        
                       
                      

  提交代码后，AC掉该题，Runtime:52 ms。