leetcode 16. 最接近的三数之和

题目描述

给定一个包括 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

解题思路

之前做过“求一个数组中，哪两个数加起来等于target”的题，做法为双指针。这个题是找三个数，除了可以暴力O(n^3)之外，还可以用找最小的distance = target - sum(a, b, c)的思路来解决。
也就是：
1. 先排序好整个数组
2. 假设数组的长度为n，我们先枚举a，它在数组中的位置为i；
3. 为了防止重复枚举，我们在位置 range(i+1,N) 的范围内枚举B和C。
在枚举的过程中，应当做while(pb < pc)的循环：
- 如果sum(a, b, c) = target，直接找到。
- 如果sum(a, b, c) > target，此时将pc向左移动一个位置, 并判断此时是否sum(a, b, c) = target，如果不是的话，如果distance小，更新一下best_sum_result也是极好的。
- 如果sum(a, b, c) < target，此时将pb向右移动一个位置, 并判断此时是否sum(a, b, c) = target，如果不是的话，如果distance小，更新一下best_sum_result也是极好的。
最终输出best_sum_result。

解题代码

class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        sum_result = 0
        nums.sort()
        best_distance = 1000000  # 以后必然会降低这个best_distance
        for i in range(len(nums) - 2):
            if i >= 1 and nums[i] == nums[i - 1]:
                continue  # 小优化：防止nums数组前后两个数一致造成重复判断
            want = target - nums[i]
            j, k = i + 1, len(nums) - 1

            # 这段在本程序中两次出现，目的是如果distance == 0，就直接确定最终的sum_result
            if nums[j] + nums[k] == want:
                sum_result = nums[i] + nums[j] + nums[k]
                return sum_result

            # 这段在本程序中三次出现，目的是如果distance更近，就更新sum_result
            distance = abs(target - (nums[i] + nums[j] + nums[k]))
            if distance < best_distance:
                best_distance = distance
                sum_result = nums[i] + nums[j] + nums[k]

            while j < k - 1:  # -1是为了防止j == k，这样while循环终止时是j + 1 == k
                while j < k - 1 and nums[j] + nums[k] > want:
                    k -= 1
                    distance = abs(target - (nums[i] + nums[j] + nums[k]))
                    if distance < best_distance:
                        best_distance = distance
                        sum_result = nums[i] + nums[j] + nums[k]

                if nums[j] + nums[k] == want:
                    sum_result = nums[i] + nums[j] + nums[k]
                    return sum_result

                while j < k - 1 and nums[j] + nums[k] < want:
                    j += 1
                    distance = abs(target - (nums[i] + nums[j] + nums[k]))
                    if distance < best_distance:
                        best_distance = distance
                        sum_result = nums[i] + nums[j] + nums[k]
        return sum_result

执行结果

执行结果：通过
执行用时：60 ms, 在所有 Python3 提交中击败了98.25%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了45.48%的用户