给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
复制代码解法
本题的解法和15. 三数之和相似，只是比较对象从0变成了target。也是采用排序+双指针的做法。
- 如果
a+b+c ≥ target，那么就将c对应的指针向左移动一个位置 - 如果
a+b+c < target，那么就将b对应的指针向右移动一个位置
def threeSumClosest(nums, target):
nums.sort()
n = len(nums)
best = 10**7
# 根据差值的绝对值来更新答案
def update(cur):
nonlocal best
if abs(cur - target) < abs(best - target):
best = cur
# 枚举a
for i in range(n):
# 保证和上一次枚举的元素不相等
if i > 0 and nums[i] == nums[i - 1]:
continue
# 使用双指针枚举b, c
L, R = i + 1, n - 1
while L < R:
sum = nums[i] + nums[L] + nums[R]
# 如果和为target，那么它就是最接近的和，直接返回
if sum == target:
return target
update(sum) # 每次指针变化过后，更新答案
if sum < target:
# 如果和小于target，b 对应的指针向右移动一位
L0 = L + 1
# 移动到下一个不相等的元素
while L0 < R and nums[L0] == nums[L]:
L0 += 1
L = L0
else:
# 如果和大于target，c 对应的指针向左移动一位
R0 = R - 1
# 移动到下一个不相等的元素
while L < R0 and nums[R0] == nums[R]:
R0 -= 1
R = R0
return best
复制代码复杂度分析
- 时间复杂度：O(N^2)，其中 N 是数组 nums 的长度。我们首先需要 O(NlogN) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(N) 枚举 a，双指针 O(N) 枚举 b 和 c，故一共是 O(N^2)。
- 空间复杂度：O(logN)。排序需要使用 O(logN) 的空间。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，此时空间复杂度为 O(N)。
