LeetCode15. 三数之和｜刷题打卡

太过爱你忘了你带给我的痛 2022-11-05 08:44 132阅读 0赞

# 一、题目描述 #

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

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

**示例 1：**

输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]

**示例2：**

输入：nums = []
    输出：[]

**示例 3：**

输入：nums = [0]
    输出：[]

**提示：**

*  0 <= nums.length <= 3000
 *  \-10^5 <= nums\[i\] <= 10^5

# 二、思路分析 #

三数之和，看完题目先思考，千万不能萌生了要三层循环的想法。

我们可以把**求和问题变成求差问题**：

固定其中一个数，在剩下的数中寻找是否有两个数和这个固定数相加是等于0的。

*  先将数组排序（有序数组中可以利用双指针来缩小定位范围）
 *  再利用双指针来处理两数之和
 *  相加之和大于0，说明右侧的数偏大了，右指针左移
 *  相加之和小于0，说明左侧的数偏小了，左指针右移
 *  注意跳过重复元素

![7d6ad6fe2a5335c4525797ff19b070d4.png][]

# 三、AC 代码 #

/**
     * @param {number[]} nums
     * @return {number[][]}
     */
    const threeSum = function(nums) {
        // 用于存放结果数组
        let res = [] 
        // 给 nums 排序
        nums = nums.sort((a,b)=>{
            return a-b
        })
        // 缓存数组长度
        const len = nums.length
        // 注意我们遍历到倒数第三个数就足够了，因为左右指针会遍历后面两个数
        for(let i=0;i<len-2;i++) {
            // 左指针 j
            let j=i+1 
            // 右指针k
            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++
                    }
                } else if(nums[i]+nums[j]+nums[k]>0){
                    // 三数之和大于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
    };

# 四、总结 #

*  三数之和，可以把求和问题变成求差问题——固定其中一个数，在剩下的数中寻找是否有两个数和等于这个固定数和目标数的差。
 *  有序数组中双指针根本能帮助我们缩小定位的范围。

[7d6ad6fe2a5335c4525797ff19b070d4.png]: /images/20221023/41a184903436493594b28ff317c3bb4c.png