15. 三数之和

1. 题目描述

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

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

示例：

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

2. 解题思路

这个题和之前的两数之和完全不一样，不过这里依旧可以使用双指针来实现。

我们在使用双指针时，往往数组都是有序的，这样才能不断缩小范围，所以我们要对已知数组进行排序。
（1）首先我们设置一个固定的数，然后在设置两个指针，左指针指向固定的数的后面那个值，右指针指向最后一个值，两个指针相向而行。
（2）每移动一次指针位置，就计算一下这两个指针与固定值的和是否为0，如果是，那么我们就得到一组符合条件的数组，如果不是0，就有一下两种情况：

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

（3）按照上边的步骤，将前len-2个值依次作为固定值，最终得到想要的结果。

因为我们需要三个值的和，所以我们无需最后两个值作为固定值，他们后面已经没有三个值可以进行计算了。

3. 代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
   let res = []
   let sum = 0
   // 将数组元素排序
   nums.sort((a,b) => {
       return a-b
   })
   const len =nums.length
   for(let i =0; i<len-2; i++){
       let j = i+1
       let k = len-1
       // 如果有重复数字就跳过
       if(i>0&& nums[i]===nums[i-1]){
           continue
       }
       while(j<k){
           // 三数之和小于0，左指针右移
           if(nums[i]+nums[j]+nums[k]<0){
               j++
               // 处理左指针元素重复的情况
               while(j<k&&nums[j]===nums[j-1]){
                   j++
               }
            // 三数之和大于0，右指针左移
           }else if(nums[i]+nums[j]+nums[k]>0){
               k--
               // 处理右指针元素重复的情况
               while(j<k&&nums[k]===nums[k+1]){
                   k--
               }
           }else{
               // 储存符合条件的结果
               res.push([nums[i],nums[j],nums[k]])
               j++
               k--
               while(j<k&&nums[j]===nums[j-1]){
                   j++
               }
               while(j<k&&nums[k]===nums[k+1]){
                   k--
               }
           }
       }
    }
    return res
};

4. 提交结果