https://leetcode-cn.com/problems/3sum-closest/
和上一题15. 3Sum 差不多,用三个游标i, front, back分别遍历,用minDist = sum - target记录与target最接近的和。最后若跳出循环,说明没有找到恰好等于target的和,没关系,由于记录了最接近target的距离minDist,返回值用sum = minDist + target即可。
与15. 3sum的区别:上一题front和back在找到sum为0的一个组合后,可以跳过相同的元素,而本题中若没有找到和为0的组合,就令front和back跳过,可能会遗漏某些组合。因此只有i可以跳过元素,另两个不行
例如[0,1,1,55] i=0,front=(第一个)1,back=55 此时若认为front前面有相同元素,就令front+1,则front的前进会挤占back的搜索空间,使得back无法等于1,这是不对的。为什么3sum中不会出现front挤占back的搜索空间?因为数组首先经过了排序,i不变,要找和为0,front前移,back必须回退,才能找到下一个和为0组合,例如back回退到1,也不可能和front=1组合
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
minDist = sys.maxsize
i = 0
while i < len(nums):
front, back = i+1, len(nums)-1
while front < back:
sum = nums[i] + nums[front] + nums[back]
if abs(sum - target) < abs(minDist): #更新
minDist = sum - target
if sum < target:
front += 1
elif sum > target:
back -= 1
else: #刚好等于,直接返回
return sum
while i+1 < len(nums) and nums[i] == nums[i+1]:
i += 1 #跳过相同的元素(不知道为啥能跳
i += 1
return target + minDist