2021-09-05 Leetcode 15. 三数之和
2021/9/5 23:37:58
本文主要是介绍2021-09-05 Leetcode 15. 三数之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:
暴力求解,3重循环.
时间复杂度:O(n^3)
这个解法超过了Leetcode的运行时间限制.无法提交.
解法二,双指针法:
先对nums排序(升序).平均时间复杂度O(n*log(n))
为了方便,我把a数字与a数字的数组下标混在一起说了.以下所有说到右移++、左移–,都指的是数组下标的操作.
设定a<b<c,第一重循环遍历a.
关键在第二重循环.b从a+1开始,自左向右递增.c从最右侧开始,自右向左递减.
- 如果a+b+c==0,找到结果.则b++.由于b右移变大了,为了满足a+b+c=0,于是c–.
- 如果a+b+c>0并且b<c,则c–.这个好理解.
- 如果b==c,则说明a+b+(b+1)>0.此时b右移没有意义,因为a+(b+1)+(b+2)也必然大于0. 因此要跳到第一重循环a++.
- 如果a+b+c<0,结合条件1、2,隐含说明a+b+(c+1)>0.此时b右移没有意义,因为a+(b+1)+(c+1)也必然大于0.因此要跳到第一重循环a++.
综上,第二重循环可以概括为如下伪代码:
while(b<c && a+b+c>0) c--; if(b==c) //由于上面的if先判断b<c,因此这里要先过滤b==c的情况.不能与下边的if调换顺序 break; if(a+b+c==0) 存结果; c--; continue; else //a+b+c<0 break;
可以发现,b与c,一个向右,一个向左,直到两者相遇.它们的移动没有嵌套的循环关系.因此第二层循环的时间复杂度就是O(n).
再考虑第一层循环的嵌套关系,整体时间复杂度是O(n^2)
这篇关于2021-09-05 Leetcode 15. 三数之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain