16. 最接近的三数之和

题目

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

返回这三个数的和。

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

示例 1：

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

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

解答

思路

代码

Python 代码

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        min_diff = inf
        ans = 0

        for i in range(n - 2):
            x = nums[i]
            
            if i > 0 and x == nums[i - 1]:
                continue
            
            s = x + nums[i + 1] + nums[i + 2]
            if s > target:
                if s - target < min_diff:
                    ans = s
                break
            
            s = x + nums[-2] + nums[-1]
            if s < target:
                if target - s < min_diff:
                    min_diff = target - s
                    ans = s
                continue
            
            j = i + 1
            k = n - 1

            while j < k:
                s = x + nums[j] + nums[k]
                
                if s == target:
                    return s
                
                if s > target:
                    if s - target < min_diff:
                        min_diff = s - target
                        ans = s
                    
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
                else:
                    if target - s < min_diff:
                        min_diff = target - s
                        ans = s
                    
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
            
        return ans