LeetCode_Python(16)_最接近的三数之和

需求

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。

假定每组输入只存在唯一答案。

例如：
给定数组 nums = [-1，2，1，-4]、 target = 1.
与 target 最接近的三个数的和为：2
解释：-1 + 2 + 1 = 2

方法一：排序 + 双指针

1. 排序后，先考虑3种特殊情况：
   序列长度为3时直接返回
   最大的3位之和小于等于target时，直接返回
   最小的3位之和大于等于target时，直接返回

2. 和(15)题的思路一样，遍历序列，从头部和尾部通过双指针，进行判断，每次遍历结果取最小差值，即为最近距离；

3. 参考代码

def three_sum_closest(nums, target):
    nums.sort()

    # three special case
    if len(nums) == 3: return sum(nums)
    if sum(nums[-3:]) <= target: return sum(nums[-3:])
    if sum(nums[:3]) >= target: return sum(nums[:3])

    res = nums[0] + nums[1] + nums[-1]
    for i in range(len(nums) - 2):
        l = i + 1
        r = len(nums) - 1

        if i > 0 and nums[i] == nums[i - 1]: continue

        while l < r:
            cur = nums[i] + nums[l] + nums[r]
            if abs(cur - target) < abs(res - target): res = cur 
            elif cur == target: return res
            elif cur > target: r -= 1
            else: l += 1

    return res 

nums = [-1, 3, -4, 5, -6, 1]
target = 1
print(three_sum_closest(nums, target))
0

方法二：暴力法超时

1. 使用itertools模块中的combinations()函数，对数组中的元素进行组合，并求得每个组合之和；
2. 同样的方法，通过列表推导式求得三个数之和与target最近的值；
3. 由于只存在唯一答案，遍历每个组合之和，直到组合之和减去最近的值等于target时，直接返回组合之和即可。

参考代码

from itertools import combinations

def three_sum_closest(nums, target):
    # 所有的3个整数之和
    sum_list = [sum(x) for x in combinations(nums, 3)]
    # 所有的3个整数之和与target最接近的值
    min_close = min(abs(sum(x) - target) for x in list(combinations(nums, 3)))
    for i in sum_list:
        if abs(i - target) == min_close:
            return i 

nums = [-1, 2, 1, -4]
target = 1 
print(three_sum_closest(nums, target))
2