需求
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。
假定每组输入只存在唯一答案。
例如：
给定数组 nums = [-1，2，1，-4]、 target = 1.
与 target 最接近的三个数的和为：2
解释：-1 + 2 + 1 = 2
方法一：排序 + 双指针
排序后，先考虑3种特殊情况：
序列长度为3时直接返回
最大的3位之和小于等于target时，直接返回
最小的3位之和大于等于target时，直接返回和(15)题的思路一样，遍历序列，从头部和尾部通过双指针，进行判断，每次遍历结果取最小差值，即为最近距离；
参考代码
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
方法二：暴力法超时
- 使用
itertools模块中的combinations()函数，对数组中的元素进行组合，并求得每个组合之和； - 同样的方法，通过列表推导式求得三个数之和与target最近的值；
- 由于只存在唯一答案，遍历每个组合之和，直到组合之和减去最近的值等于
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
