【LeetCode】（No.016）最接近的三数之和
【LeetCode】（No.016）最接近的三数之和
PM小王
发布于 2019-07-02 16:17:47
发布于 2019-07-02 16:17:47
NO.16 最接近的三数之和
一、写在前面
刷题已经断更好几天了，主要原因最近参加了机器学习的比赛忙着处理特征值优化自己的模型，刷题其实挺耗时间的，而且看得人也不是很多，所以最近自己也没有怎样刷题，不管自己的公众号怎样变刷题这个模块一定会保留下去，期待自己能成为offer收割机。LeetCode 第十五题三数之和传输门：【LeetCode】（No.015）三数之和今天给大家分享的是LeetCode 第十六题：最接近的三数之和，为面试而生，期待你的加入。
二、今日题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组
nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为
2. (-1 + 2 + 1 = 2).三、 分析
这个题目跟之前的两数之和，三数之和都是相似的，因此代码也是在三数之和的基础上修改的。只不过因为需要求最近的，而不是固定的，因此所有的判定都需要修改为判断与与target做差后的绝对值， 因为代码大构架和三数之和类似。忘记思路的可以看看之前的文章【LeetCode】（No.015）三数之和
四、解题
nums.sort()
res = sum(nums[:3])
m = abs(res - target)
for i in range(len(nums)):
l = i+1
r = len(nums)-1
while l < r:
temp = nums[i] + nums[l] +nums[r]
if abs(res - target) > abs(temp-target):
res = temp
elif target < temp:
r -=1
else :
l +=1
return res
这种方法的执行时间真的很差，自己肯定是不满足的，然后对代码做了优化。
nums.sort()
res = []
for i, v in enumerate(nums[:-2]):
l, r = i + 1, len(nums) - 1
if v + nums[r - 1] + nums[r] < target:
res.append(v + nums[r - 1] + nums[r])
elif v + nums[l] + nums[l + 1] > target:
res.append(v + nums[l] + nums[l + 1])
else:
while l < r:
total = v + nums[l] + nums[r]
res.append(total)
if total < target:
l += 1
elif total > target:
r -= 1
else:
return target
res.sort(key=lambda x: abs(x - target))
return res[0]
执行时间还不错。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录