【刷题第七天】15 三数之和

2022 年 5 月 13 日
本文字数：1186 字
阅读完需：约 4 分钟

一、题目描述：

给你一个包含 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,0,0,0,0]复制代码

复制代码

数组中全是重复 0 ，这样我们无法通过简单的三重循环来遍历出所有的满足情况。

其实题解的方法还是借鉴了两数之和的我的第一种想法，即双指针扫描法。但是题解用的很巧妙，题解是这么做的:

首先我们来分析如何能保证不重复:

第二重循环枚举的元素索引大于第一重循环枚举的元素索引
第三重循环枚举的元素索引大于第二重循环枚举的元素索引

也就是说我们最终枚举的三元组 (x,y,z) 满足 x <= y <= z，由于我们限制了顺序，所以就可以保证此三元组的唯一性，避免了重复。

那我们应该如何实现上面的想法呐:

临界判断，判断数组为空或者其长度小于 3，直接返回空数组
对数组进行排序(是不是越来越像两数之和了)
开始遍历数组:如果 nums[i] + nums[L] + nums[R] > 0，说明当前三数之和过大，因此左移 R 减小三数之和如果 nums[i] + nums[L] + nums[R] < 0，说明当前三数之和过大，因此右移 L 增大三数之和如果 nums[i] + nums[L] + nums[R] = 0，说明当前三数之和正好，将当前三元组压入到 res 数组执行
当 L>=R 时跳出循环
for 循环遍历完毕，输出所有的三元组

三、AC 代码：

var threeSum = function(nums) {  let res = [];  if(nums.length < 3) return res; // 判断临界条件  nums.sort((a, b) => a - b); // 对数组进行排序  for (let i = 0; i < nums.length-2 ; i++) {    if(nums[i] > 0) break; // 当 nums[i] > 0，后续不可能出现等于0情况    if(i > 0 && nums[i] == nums[i-1]) continue; // 跟右侧进行判断，避免重复    let L = i+1;    let R = nums.length-1;    while(L < R) { // Case 3      const cnt = nums[i] + nums[L] + nums[R];      if(cnt == 0){        res.push([nums[i],nums[L],nums[R]]);         while (L<R && nums[L] == nums[L+1])  { // 避免重复           L++;        };          while (L<R && nums[R] == nums[R-1]){ // 避免重复          R--;        };         L++;        R--;      }      else if (cnt < 0) { // Case 2           L++;      } else if (cnt > 0) { // Case 1          R--;      };    }  }          return res;};复制代码

复制代码

四、总结：

刷题真是道阻路且长，好难啊，加油加油啊。最近的刷题总是会少考虑一点，导致全盘崩溃，我麻了。

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/356f79131980426ac69ce20b5】。文章转载请联系作者。

白日梦

关注

还未添加个人签名 2022.03.10 加入

还未添加个人简介

发布

暂无评论

创作场景

【刷题第七天】15 三数之和

一、题目描述：

示例 1：

示例 2:

示例 3:

二、思路分析：

三、AC 代码：

四、总结：

白日梦

评论