ericpuwang

最接近的三数之和

https://leetcode.cn/problems/3sum-closest/description/

给你一个长度为n的整数数组nums和目标值target.请你从nums中选出三个整数，使他们的和最接近target, 返回这三个数的和 NOTE: 假定每组输入只存在恰好一个解。

示例1

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例2

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) == 3:
            return sum(nums)

        nums.sort()
        min_diff = abs(target - sum(nums[:3]))
        res = sum(nums[:3])
        for index, num in enumerate(nums[:-2]):
            # nums[index-1]已经计算过,避免重复计算
            if index and num == nums[index-1]:
                continue

            # 大于target的数值中的最小数
            s = num + nums[index+1] + nums[index+2]
            if s > target:
                if s - target < min_diff:
                    res = s
                break

            # 小于target的数值中的最大数
            # nums中索引大于index的任意两数之和都小于target
            s = num + nums[-1] + nums[-2]
            if s < target:
                if target - s < min_diff:
                    min_diff = target - s
                    res = s
                continue

            j = index + 1
            k = len(nums) - 1
            while j < k:
                s = num + nums[j] + nums[k]
                if s == target:
                    return s
                elif s > target:
                    k -= 1
                else:
                    j += 1
                if abs(target - s) < min_diff:
                    min_diff = abs(target - s)
                    res = s
        return res