题目描述

[EN | CN]

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

1
2
3
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法 1:三指针

显然,最暴力的解法是套 3 层循环,时间复杂度为 $O(n^3)$,这明显是不可接受的。既然要求三数之和距离 target 最近,这个要求其实跟《⌨️ LeetCode 015. 三数之和》(本博客)的差别不大,区别在于是那道题要求「刚刚好」,本题要求「保存一个当前最接近的方案」。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n^2)$;
  • 空间复杂度为 $O(1)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        min_diff = 10000
        ret = 10000

        for a in range(len(nums) - 2):
            b = a + 1
            c = len(nums) - 1

            while b < c:
                sum_ = nums[a] + nums[b] + nums[c]
                diff = sum_ - target

                if diff == 0:
                    return target

                if abs(diff) < min_diff:
                    min_diff = abs(diff)
                    ret = sum_

                if diff < 0:
                    b += 1
                else:
                    c -= 1

        return ret
  • 执行用时:116 ms,在所有 Python3 提交中击败了 76.89% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.05% 的用户。