16. 最接近的三数之和

引流：五点钟科技-CSDN博客?

题目：

给你一个长度为?n?的整数数组?nums?和 一个目标值?target。请你从?nums?中选出三个整数，使它们的和与?target?最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

【解题思路】

遇到这种x数之和的问题，不要纠结，优先考虑多指针的解法。本题和【三数之和?】并没有本质上的区别，唯一的区别在于其判断条件变了，这里是要在数组中寻找3个数之和与某个数的距离，在三数之和的题中，是寻找三个数与0之间的关系，很明显的，当target为0时，题目就蜕变成三数之和的问题了，只不过此处是求最“接近”而非“等于”。

既然如此，我们只需要在三数之和的判断条件中，将if的左边项减去一个target，右边仍然保持为0，形式上就还是三数之和的“三段式判别法”，即<0的情况、>0的情况以及=0的情况，这是在判断什么呢？当然是判断第二个指针和第三个指针如何移动的问题啦，显然，当三数之和与target的差值为负数时，说明差值过大，所以第二个指针需要往大的方向移动（向右移动），当三数之和与target的差值为正数时，同理需要第三个指针向左移动，当差值为0时，两个指针同时向内移动一步。那么“最接近”该怎么判断呢？也很好理解，既然是最接近，那必然是求距离的问题，要求最小距离，我们设置一个变量minx来始终记录距离最小的值，因此我们只需要在三段式判别之下再多一个判断，即判断当前三数之和与target之差的绝对值是否小于minx即可，显然，当当三数之和与target的差值为0时，说明三数之和直接等于target，距离达到最小，为0，那么minx就为0。

【代码】

def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) == 3:
            return sum(nums)
        n = len(nums)-1
        minx = float('inf')
        nums.sort()
        for cur in range(n-1):
            left = cur + 1
            right = n
            while left < right:
                if nums[cur] + nums[left] + nums[right] - target < 0:
                    if abs(nums[cur] + nums[left] + nums[right] - target) < minx:
                        minx = abs(nums[cur] + nums[left] + nums[right] - target)
                        res = nums[cur] + nums[left] + nums[right]
                    left += 1
                elif nums[cur] + nums[left] + nums[right] - target == 0:
                    minx = 0
                    res = nums[cur] + nums[left] + nums[right]
                    left += 1
                    right -= 1
                else:
                    if abs(nums[cur] + nums[left] + nums[right] - target) < minx:
                        minx = abs(nums[cur] + nums[left] + nums[right] - target)
                        res = nums[cur] + nums[left] + nums[right]
                    right -= 1
        return res

?