【lc刷题】16 最接近的三数之和_Day08(26/300)
26/300
- 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
因为刚做了3Sum,这题感觉思路不错,把不够格的nums和重复的都考虑到了,满怀信心点击提交,超出时间限制,看到input是:[0,1,2] 3
。这不就是所用即所求嘛,果断加上一行如果相等就返回target,遂通过。
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
if n < 3: return
nums.sort()
#initialize
closed_target = sum(nums[:3])
for i in range(n-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l = i + 1
r = n - 1
while l < r:
tmp_sum = nums[i] + nums[l] + nums[r]
if tmp_sum == target: return target #不加这行就时间超限
if abs(target - tmp_sum) < abs(target - closed_target):
closed_target = tmp_sum
if tmp_sum > target: r -= 1
elif tmp_sum < target: l += 1
return closed_target