【Leetcode刷题Python】16. 最接近的三数之和
2023-09-14 09:12:59 时间
1 题目
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1
输出:0
2 解析
和15题三数之和,遍历思路几乎是一样的思想
参考【15.三数之和】的思路
用一个min_flag 和result记录最小差值和最小差值对应的和
如果当前的差值比min_flag小,就替换,并且保留当前三个数的和。
3 Python实现
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
if n<3:
return nums.sum()
nums.sort()
min_gap = 0
result = nums[0]+nums[1]+nums[2]
for i in range(n-1):
l = i+1
r =n-1
while l<r:
sum = nums[l] +nums[i]+nums[r]
gap = sum -target
min_gap = abs(target-result)
# 判断新组合是否超过最小值
if min_gap > abs(gap):
result = sum
if gap >0:
r-=1
elif gap<0:
l+=1
else:
return result
return result
相关文章
- python面试题
- python实现FTP弱口令扫描器与简单端口扫描器
- Python MySQLdb模块连接操作mysql数据库实例_python
- Python 刷Leetcode题库,顺带学英语单词(1)
- 学习Python的10大刷题网站,寓教于乐适合自学
- Python之matplotlib:基于matplotlib库利用python语言实现一张画布显示多张图的多种方法
- Python之ffmpeg:利用python编程基于ffmpeg将m4a格式音频文件转为mp3格式文件
- Python之tkinter:动态演示调用python库的tkinter带你进入GUI世界(Entry/Entry的Command)
- Python可视化数据分析01、python环境搭建
- 〖Python 数据库开发实战 - Python与MySQL交互篇⑭〗- 项目实战 - 实现新闻管理 - 审批新闻 功能
- 使用Python进行压缩与解压缩
- python 找出数组重复的元素
- 【LeetCode Python实现】43. 字符串相乘(中等)
- 终极PK | Python和Java哪个语言更有前途?
- python接口测试之mock(三)
- Python 头部 #!/usr/bin/python 和 #!/usr/bin/env 的区别
- 【Leetcode刷题Python】232. 用栈实现队列
- 【Leetcode刷题Python】946. 验证栈序列
- 【Leetcode刷题Python】134. 加油站
- 【Leetcode刷题Python】376. 摆动序列
- 【Leetcode刷题Python】113. 路径总和 II
- 【Leetcode刷题Python】300. 最长递增子序列
- 【python 11】super()
- Python(17):Numpy之array数组的排序
- 百度网盘python客户端——筑梦之路
- Python常用内置函数(python 3.x)