三数之和

介绍

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

例如

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

题解

在leetCode中，这道题其实与两数之和那题一样，思路我感觉很像。首先当然是暴力破解法，其次是空间换时间，首先暴力破解法就 是三层遍历，四数之和就是四层遍历，所以叫暴力破解法，也是效率比较低的一种方法。那么三数之和的空间换时间要怎么理解呢。

首先给数组排个序，从小到大，然后固定其中一个值，然后定义首尾两个指针，当第一个数大于0 或者最后一个数小于0的时候，直接跳过，因为这样相加怎么都不可能等于0， 只有第一个数小于0，首指针小于尾指针的时候再去判断这三个数相加是否等于0，如果等于0，返回这三个数，然后首尾指针移动，下面看看实际代码例子，都有注释

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  //用来存取最后结果集
    let result = [];
    //头指针
    let head=null;
    //尾指针
    let end=null;
    //固定值
    let fixedVal=null;

    //排序
    nums.sort((a, b) => {
        return a-b;
    });
    
    //判断数组内元素是否都为整数或负数，直接返回
    if(nums[0] > 0 || nums[nums.length - 1] < 0) return result;
    
    // 开始遍历
    for (let i = 0; i < nums.length; i++) {
        //固定值
        fixedVal = nums[i];
        // 如果前后元素相同，跳过此次循环（固定值）
        if(fixedVal === nums[i-1]) continue;
        //一开始的固定值为nums[0],所以头指针为 i+1 下一个元素
        head = i+1;
        //尾指针
        end = nums.length - 1;
        //如果头指针小于尾指针元素
        while(head < end){
            //判断固定值+头指针+尾指针是否等于0
            if(nums[head] + nums[end] + fixedVal === 0){
                //声明数组，存放这三个值
                let group = [];
                group.push(nums[head]);
                group.push(nums[end]);
                group.push(fixedVal);
                result.push(group);
                //存放完毕之后，不要忘记头指针和尾指针的移动(否则会产生死循环)
                head += 1;
                end -= 1;
                //如果头指针满足小于尾指针且移动后的指针和移动前的指针元素相等，再往前移动
                while(head < end && nums[head] === nums[head - 1]){
                    head += 1;
                }
                 //如果头指针满足小于尾指针且移动后的指针和移动前的指针元素相等，再往后移动
                while(head < end && nums[end] === nums[end + 1]){
                    end -= 1;
                }
             //小于 0 需要移动头指针，因为尝试着让数据比原有数据大一点
            }else if(nums[head] + nums[end] + fixedVal < 0){
                head++;
            }else{
                //否则，尾指针向前移动，让数据小于元数据
                end--;
            }
        } 
    }
    return result;
};