如何用Python解决三数之和的题目
Admin 2022-09-09 群英技术资讯 453 次浏览
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,
使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
答案中不允许包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[ [-1, 0, 1], [-1, -1, 2] ]
1. 首先将数组排序,可以利用Python内置函数,也可以利用另外定义排序算法。
2. 应用双指针算法。固定第一个数,索引为i,遍历整个数组,第一个数也是三个数中最小的数,然后在该数右面设置左右两个指针l和r,l=i+1,r=len(nums)-1,
3. 判断这三个索引指向的元素和与0的大小关系。
和>0,右指针左移一位;和<0,左指针右移一位。
由于要避免重复的三元组,所以移动左右指针的时候要跳过相邻的所有相等的nums[i]。
#导入计算时间的包,调用系统时间 from time import * #初始时间 t1 = time() def threeSum(nums): nums.sort() n = len(nums) res = [] for i in range(n): '''如果相邻的两个数相等,跳过,避免重复''' if i > 0 and nums[i] == nums[i-1]: continue l, r = i+1, n-1 while l < r: if nums[i] + nums[l] + nums[r]>0: r -= 1 while nums[r+1] == nums[r]: r -= 1 elif nums[i] + nums[l] + nums[r]<0: l += 1 while nums[l-1] == nums[l]: l += 1 else: res.append([nums[i],nums[l],nums[r]]) l += 1 r -= 1 while nums[l] == nums[l - 1]: l += 1 while nums[r] == nums[r + 1]: r -= 1 return res if __name__ == '__main__': nums = [-1,0,1,2,-1,-4] print(threeSum(nums)) #结束时间 t2 = time() #运行时间 run_time = t2 - t1 print(run_time)
运行结果:
[[-1, -1, 2], [-1, 0, 1]]
#运行时间
0.0010113716125488281
以上代码有一些思想错误:
遗漏了如果三个数全部大于0,则退出循环,因为没有满足条件的结果。
没有严格判断每一次的l<r的条件。
修正后的代码:
from time import * t1 = time() def threeSum(nums): nums.sort() n = len(nums) res = [] for i in range(n-2): if nums[i] > 0:break '''如果相邻的两个数相等,跳过,避免重复''' if i > 0 and nums[i] == nums[i-1]: continue l, r = i+1, n-1 while l < r: if nums[i] + nums[l] + nums[r]>0: r -= 1 while l < r and nums[r-1] == nums[r]: r -= 1 elif nums[i] + nums[l] + nums[r]<0: l += 1 while l < r and nums[l] == nums[l-1]: l += 1 else: res.append([nums[i],nums[l],nums[r]]) l += 1 r -= 1 while l < r and nums[l] == nums[l - 1]: l += 1 while l < r and nums[r] == nums[r + 1]: r -= 1 return res if __name__ == '__main__': nums = [-2,-3,0,0,-2] print(threeSum(nums)) t2 = time() run_time = t2 - t1 print(run_time)
结果:
[]
#时间
0.0
关于“如何用Python解决三数之和的题目”的内容今天就到这,感谢各位的阅读,大家可以动手实际看看,对大家加深理解更有帮助哦。如果想了解更多相关内容的文章,关注我们,群英网络小编每天都会为大家更新不同的知识。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。
猜你喜欢
这篇文章主要介绍了教你利用Python+Turtle绘制简易版爱心表白,文中有非常详细的代码示例,对想要和男朋友或者女朋友表白的小伙伴们有很大帮助哟,需要的朋友可以参考下
本文主要介绍了python [::-1] [::-1,::-1]的具体使用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
python中常用的excel模块库有几种?怎样安装?学习python对excel模块有一定的了解还是很有必要的,下面我们就来看看常见的excel模块库有什么特点以及要如何安装。
所谓魔法函数(Magic Methods),是Python的⼀种⾼级语法,允许你在类中⾃定义函数(函数名格式⼀般为__xx__),并绑定到类的特殊⽅法中。⽐如在类A中⾃定义__str__()函数,则在调⽤str(A())时,会⾃动调⽤__str__()函数,并返回相应的结果
这篇文章主要介绍了Python数据分析之PMI数据图形展示,文章介绍了简单的python爬虫,并使用numpy进行了简单的数据处理,最终使用 matplotlib 进行图形绘制,实现了直观的方式展示制造业和非制造业指数图形,需要的朋友可以参考一下
成为群英会员,开启智能安全云计算之旅
立即注册Copyright © QY Network Company Ltd. All Rights Reserved. 2003-2020 群英 版权所有
增值电信经营许可证 : B1.B2-20140078 粤ICP备09006778号 域名注册商资质 粤 D3.1-20240008