【LeetCode】16.最接近的三数之和

1 问题

给你一个长度为 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

2 答案

自己写的，不对

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)

        if not nums or n < 3:
            return None

        min_ne = inf  
        nums.sort()
        for i in range(n):
            L = i + 1
            R = n - 1
            while L < R:
                if abs(nums[i]+nums[L]+nums[R] - target) < min_ne:
                    min_ne = abs(nums[i]+nums[L]+nums[R] - target)
                    res = nums[i]+nums[L]+nums[R]
                L += 1
                R -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

官方解，与上一题类似，依然是双指针

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        res = inf  
        nums.sort()
        for i in range(n):
            L = i + 1
            R = n - 1
            while L < R:
                tmp = nums[i]+nums[L]+nums[R]
                res = tmp if abs(tmp - target) < abs(res - target) else res # 保存res，距离每次重新算
                if tmp == target:  # 这个要有，拿tmp比，而不是res，不然指针会乱走
                    return target
                if tmp < target:
                    L += 1
                if tmp > target:
                    R -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18