给定一个包括n个整数的数组nums和一个目标值target。找出nums中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
题意分析：
3Sum问题的变种，找出3数之和使其离target最近。
思路分析：
显然，我们仍然可以用3Sum的思路来解决这道题，如果不知道本身3Sum的思路可以看这篇博客
首先对数组进行排序，固定住第一个数，然后在剩下的有序数组中将问题转换成2Sum Closest
那么我们直接解决2Sum Closest问题即可(双指针法)。
1 | def twoSumClosest(nums,target): |
ok，现在来解决3Sum Closest问题，注意处理一些终止条件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
28
29
30# 188ms, beats
class Solution(object):
def twoSumClosest(self, nums,target):
# 认为nums此时有序
n = len(nums)
i,j = 0,n-1
res = float('inf')
while i < j:
dis = nums[i] + nums[j] - target
if abs(dis) < abs(res): res = dis
if nums[i] + nums[j] == target: return target
if nums[i] + nums[j] < target: i += 1
else: j -= 1
return res + target
def threeSumClosest(self, nums, target):
nums.sort()
n = len(nums)
res = float('inf')
for i in range(n-2): # 预留两个数，否则没法双指针
if nums[i] + nums[i+1] + nums[i+2] > target:
rec = nums[i] + nums[i+1] + nums[i+2] - target
elif nums[i] + nums[n-2] + nums[n-1] < target:
rec = nums[i] + nums[n-2] + nums[n-1] - target
else:
rec = nums[i] + self.twoSumClosest(nums[i+1:], target-nums[i]) - target
if abs(rec) < abs(res): res = rec
return res + target
或者写到一起，直接在3Sum中用双指针1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# 32ms, beats 98.37%
class Solution(object):
def threeSumClosest(self, nums, target):
nums.sort()
res = float('inf')
for i in range(len(nums)-2):
j,k = i+1,len(nums)-1
if nums[i] + nums[j] + nums[j+1] >= target:
rec = nums[i]+nums[j]+nums[j+1] - target
elif nums[i] + nums[k-1] + nums[k] <= target:
rec = nums[i]+nums[k-1]+nums[k] - target
else:
while j < k:
rec = (nums[i]+nums[j]+nums[k]-target)
if abs(rec) < abs(res): res = rec
if nums[i]+nums[j]+nums[k] < target:
j += 1
elif nums[i]+nums[j]+nums[k] > target:
k -= 1
else: return target
if abs(rec) < abs(res):
res = rec
return res + target