LeetCode-16 最接近的三数之和

发表于 | 分类于 | 评论数： | 阅读次数：

题目：最接近的三数之和

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

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

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

思路

这题和之前的三数之和类似，在遍历是比较保留与target最近接的值即可。

  • 使用sort()方法进行排序，如果长度小于3直接返回sum(nums)
  • 初始化三数之和为out_sum=None
  • 依次取i为第0到len(nums)-2个数作为第一个数num1
    • 为了防止重复，如果i不是0的情况下，当前num1与上一轮的num1相同则跳过
    • 初始化第2个数的index为l，第三个数的index为r=len(nums)-1
    • 在确保l<r的情况下开始移动
      • 如果out_sum为None，即第一次遍历，或者out_sum与target的距离比当前三数之和temp_sum大，则将temp_sum赋值给out_sum
      • 如果当前三数之和等于target：直接返回，必定是最接近target的值
      • 如果当前三数之和大于target：r向左移动
      • 如果当前三数之和小于target：l向右移动

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3:
            return sum(nums)
        nums.sort()
        out_sum = None
        for i in range(0, len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                temp_sum = nums[i] + nums[l] + nums[r]
                if out_sum is None or abs(out_sum - target) > abs(temp_sum - target):
                    out_sum = temp_sum
                    continue
                if temp_sum == target:
                    return temp_sum
                elif temp_sum > target:
                    r -= 1
                else:
                    l += 1
        return out_sum

如果大家有更好的方法，欢迎一起探讨。