【亡羊补牢】挑战数据结构与算法 第72期 LeetCode 15. 三数之和(双指针)
发布日期:2021-06-29 14:34:51
浏览次数:2
分类:技术文章
本文共 1612 字,大约阅读时间需要 5 分钟。
仰望星空的人,不应该被嘲笑
题目描述
给你一个包含 n 个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],满足要求的三元组集合为:[ [-1, 0, 1], [-1, -1, 2]]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
因为不能有重复的解,为了简化操作,我们先对数组排序,于是判断一个元素是否重复,只需看它和它前面的元素是否相等即可
双指针的移动时,避免出现重复解
得到一个解后,需要左右指针向 “内” 收缩,为了避免指向重复的元素
- 左指针要在 left < right 的前提下,一直右移,直到指向不重复的元素
- 右指针要在 left < right 的前提下,一直左移,直到指向不重复的元素
优化点,如果当前元素值大于0了,由于我们事先排好序了,不存在三个数相加为0了,此时直接break就好了。
/** * @param {number[]} nums * @return {number[][]} */var threeSum = function (nums) { let len = nums.length; if (len < 2) return []; let res = []; nums.sort((a, b) => a - b); // 从小到大进行排序 for (let i = 0; i < len - 2; i++) { if (nums[i] > 0) break; if (i > 0 && nums[i] === nums[i - 1]) continue; // 去掉重复项 let L = i + 1; let R = len - 1; while (L < R) { let sum = nums[i] + nums[L] + nums[R]; // 三数之和 if (sum === 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 (sum < 0) { L++; // 和小于0,就是左边值太小了,往右移 } else if (sum > 0) { R--; // 和大于0,就是右边值太大了,往左移 } } } return res;};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108948942 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月21日 07时44分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
高德全链路压测——语料智能化演进之路
2019-04-29
打工人到什么状态,就可以离职了?
2019-04-29
面向领域的微服务架构
2019-04-29
为什么不建议把数据库部署在Docker容器内
2019-04-29
待在小公司好多年了,微服务还没怎么玩过。。。
2019-04-29
万字长文,理解Elasticsearch和面试总结
2019-04-29
面试官:数据量很大,分页查询很慢,有什么优化方案?
2019-04-29
编写 if 时不带 else,你的代码会更好!
2019-04-29
字节跳动总结的设计模式 PDF 火了,完整版开放下载!
2019-04-29
新款 iPad 写代码 真香,包邮送一个!
2019-04-29
7年,从“游戏少年”到大厂技术总监的逆袭之路
2019-04-29
超级全面的 SpringBoot 注解介绍,每一个用途都应该清晰
2019-04-29
排名前 16 的 Java 工具类,哪个你没用过?
2019-04-29
工资倒挂也刺激不了已是咸鱼的你
2019-04-29
为何 Linus 一个人就能写出这么强的系统,中国却做不出来?
2019-04-29
计算机网络原理超详解说
2019-04-29
从面试角度分析LinkedList源码
2019-04-29
是时候捋一捋Java的深浅拷贝了
2019-04-29
冰河,能不能讲讲如何实现MySQL数据存储的无限扩容?
2019-04-29