其他
【LeetCode】（No.016）最接近的三数之和
点击上方“Ahab杂货铺”，选择“置顶公众号”
技术分享第一时间送达！
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]
执行时间还不错。
近期推荐阅读：
欢迎您的点赞和分享
▲长按关注此公众号