16. 最接近的三数之和

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