LeetCode 16. 最接近的三数之和

16. 最接近的三数之和

Difficulty: 中等

给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

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

提示：

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

Solution

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        diff = float('inf')  # 设置一个极大值
        
        for i in range(len(nums)):
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(s-target) < diff:
                    diff = abs(s-target)
                    res = s
                if s < target: l += 1  # 左指针右移
                elif s > target: r -= 1  # 右指针左移
                else: return res
        return res