真题描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路分析

三数之和延续两数之和的思路，我们可以把求和问题变成求差问题——固定其中一个数，在剩下的数中寻找是否有两个数和这个固定数相加是等于0的。

双指针法用在涉及求和、比大小类的数组题目里时，大前提往往是：该数组必须有序。否则双指针根本无法帮助我们缩小定位的范围，压根没有意义。因此这道题的第一步是将数组排序：

  1.  nums = nums.sort((a,b)=>{
  2.     return a-b
  3. })

然后，对数组进行遍历，每次遍历到哪个数字，就固定哪个数字。然后把左指针指向该数字后面一个坑里的数字，把右指针指向数组末尾，让左右指针从起点开始，向中间前进：

每次指针移动一次位置，就计算一下两个指针指向数字之和加上固定的那个数之后，是否等于0。如果是，那么我们就得到了一个目标组合；否则，分两种情况来看：

  • 相加之和大于0，说明右侧的数偏大了，右指针左移
  • 相加之和小于0，说明左侧的数偏小了，左指针右移

tips：这个数组在题目中要求了“不重复的三元组”，因此我们还需要做一个重复元素的跳过处理。

编码实现

  1. const threeSum = function(nums) {
  2.     // 用于存放结果数组
  3.     let res = [] 
  4.     // 给 nums 排序
  5.     nums = nums.sort((a,b)=>{
  6.         return a-b
  7.     })
  8.     // console.log(nums);//[ -4, -1, -1, 0, 1, 2 ]
  9.     // 缓存数组长度
  10.     const len = nums.length
  11.     // 注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
  12.     for(let i=0;i<len-2;i++) {
  13.         // 左指针 j
  14.         let j=i+1 
  15.         // 右指针k
  16.         let k=len-1   
  17.         // 如果遇到重复的数字，则跳过
  18.         if(i>0&&nums[i]===nums[i-1]) {
  19.             continue
  20.         }
  21.         while(j<k) {
  22.             // 三数之和小于0，左指针前进
  23.             if(nums[i]+nums[j]+nums[k]<0){
  24.                 j++
  25.                // 处理左指针元素重复的情况
  26.                while(j<k&&nums[j]===nums[j-1]) {
  27.                     j++
  28.                 }
  29.             } else if(nums[i]+nums[j]+nums[k]>0){
  30.                 // 三数之和大于0，右指针后退
  31.                 k--
  33.                // 处理右指针元素重复的情况
  34.                while(j<k&&nums[k]===nums[k+1]) {
  35.                     k--
  36.                 }
  37.             } else {
  38.                 // 得到目标数字组合，推入结果数组
  39.                 res.push([nums[i],nums[j],nums[k]])
  41.                 // 左右指针一起前进
  42.                 j++  
  43.                 k--
  45.                 // 若左指针元素重复，跳过
  46.                 while(j<k&&nums[j]===nums[j-1]) {
  47.                     j++
  48.                 }  
  50.                // 若右指针元素重复，跳过
  51.                while(j<k&&nums[k]===nums[k+1]) {
  52.                     k--
  53.                 }
  54.             }
  55.         }
  56.     }
  58.     // 返回结果数组
  59.     return res
  60. };
  61. console.log(threeSum([-1, 0, 1, 2, -1, -4])); //[ [ -1, -1, 2 ], [ -1, 0, 1 ] ]