15. 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: 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]]

1 /** 2  * @param {number[]} nums 3  * @return {number[][]} 4  */ 5 var threeSum = function(nums) { 6      7     //和two sum的解法一样，只不过多个循环，还有一点，注意要去重。   8     var len = nums.length; 9     10     var res = [];11 12     13     //这里有个坑，就是sort函数对于负数，是根据绝对值排的，不行你们试试 [-4,-2,-2]变成了[-2,-2,-4];14     //所以这里我加了个callback15     nums.sort(function(a,b){ return a-b;});16     17     for(var i = 0;i
     
       -4 j--> -1 k一直遍历都不行28             29         //第二种  i--> -4 j--> -1(这里其实往前走了一位的) j从0开始到2， 这种其实和第一遍一样，我们要去掉这种重复的。     30         31         //第三种  假如说 -1 0 1 已经是一组解了， 然后由于-1有2个数，这就造成重复解32         33         34         //双指针解法35         while(left < right){36                     37             var l = nums[left];38             var r = nums[right];39             var temp = l + r;40         41             //首先要保证一个解42              if(temp == target){43                  var subres = [];44                  subres.push(nums[i]);45                  subres.push(l);46                  subres.push(r);47                  48                  res.push(subres);49                                50                 //去重51                 while(nums[left] == nums[left+1]){52                 53                       left++;54               55                 }56             57                 while(nums[right] == nums[right-1]){58                 59                      right--;60               61                 }62                  63                  left++;64                  right--; 65                  66                 67              }else if(temp < target){68                  69                  left++;70                  71              }else{72                  73                  right--;74              } 75               76         }77         78         //去重79         while(i + 1 < len && nums[i] == nums[i+1]){80             81             i++;82         }83                         84     }85     return res;86 };