leetcode top100挑战, 每天不鸽一道题之三数之和(9/100)-一一网

这是我参与更文挑战的第17天，活动详情查看：更文挑战

题目描述

三数之和

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

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

leetcode-cn.com/problems/le…

// 示例1 
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
// 示例2 
输入：nums = [0]
输出：[]
复制代码

解题分析

1. 双指针

直接上讲解。

使用双指针加上遍历的元素来判断三个数字的和。

首先对数据从小打到进行排序。
然后进入遍历。



当前遍历元素为num[i],使用双指针来记录后面两端的元素。num[l], num[r]

计算三个数的和是否等于0，如果符合就加入到返回的数据集变量res中。
这边需要注意不相等的时候双指针的走向。
第一需要注意的就是，数据集已经经过排序，所以三数的和小于0，那就移动左指针，让和变大直到有结果等于0.
如果三数的和大于0，那就移动右指针，让和逐渐变小，直到有结果等于0。
然后两个指针指到的数据要判断是否重复，如果重复了就跳过验算下一个。

复制代码

来人上代码！！！！！

function threeSum(nums: number[]): number[][] {
    //如果没有超过三个数，那就回复空数组
    if(nums.length < 3) return []
    //排序
    let res: number[] [] = []
    let sortedNums: number [] = nums.sort((a,b) => a - b)
    //进入遍历
    for(let i =0; i< sortedNums.length; i++) {
        // 如果当前遍历的元素大于0，那就说明三数和一定大于0，那就没必要继续下去了
        if(sortedNums[i] > 0) break;
        //如果重复了那就跳过本次遍历
        if(i > 0  && sortedNums[i] === sortedNums[i - 1]) continue
        // 左侧和右侧的指针
        let [l, r] = [i+1, sortedNums.length - 1]
        while (l < r) {
            const sum: number = sortedNums[i] + sortedNums[l] + sortedNums[r]
            if(sum === 0) {
                // 如果和等于0，那就推进去
                res.push([sortedNums[i], sortedNums[l], sortedNums[r]])
                // 如果左指针相同，那就跳过继续跑下一个左指针
                while(l < r && sortedNums[l] === sortedNums[l + 1]) l++
                // 如果右指针相同，那就跳过继续跑下一个右指针
                while(l < r && sortedNums[r] === sortedNums[r - 1]) r++ 
                l++
                r--
            }
            // 数据集已经经过排序，所以三数的和小于0，那就移动左指针，让和变大直到有结果等于0
            else if (sum < 0) l++ 
            // 如果三数的和大于0，那就移动右指针，让和逐渐变小，直到有结果等于0
            else if (sum > 0) r--
        }
    }
    return res
};
复制代码