16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
分析：
如果使用暴力法，求取每一种三个数的组合。需要三重循环，时间复杂度达到了(O(n^3))。
仔细观察这道题目，如果对nums进行排序。就可以利用 双指针法来优化时间复杂度。
if cur_sum == target:
return cur_sum
if cur_sum < target:
left += 1
if cur_sum > target:
right -= 1
如果我们确定了原数组的排序，我们就可以明确下一步指针移动的方向。
代码（Python）：
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
res = float("inf")
ans = 0
nums.sort()
n = len(nums)
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
cur_sum = nums[i] + nums[left] + nums[right]
cur_res = abs(cur_sum - target)
# 更新答案
if cur_res < res:
res = cur_res
ans = cur_sum
# 指针的移动放在一次循环的末尾更合适一些
if cur_sum == target:
return cur_sum
elif cur_sum < target:
left += 1
else:
right -= 1
return ans