难度: Medium
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1 输出：0
提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104运行时间: 120 ms
内存: 14.9 MB
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
ans = nums[0] + nums[1] + nums[2]
n = len(nums)
for k in range(n):
i = k + 1
j = n - 1
while i < j:
s = nums[k] + nums[i] + nums[j]
if abs(s-target) < abs(ans-target):
ans = s
if s == target:
return s
elif s > target:
j -= 1
elif s < target:
i += 1
return ans
该解法采用了双指针的思路，首先将数组排序，然后固定一个元素，利用双指针在剩余的元素中寻找与目标值最接近的两个数。具体步骤如下： 1. 对数组进行排序。 2. 遍历数组，对于每个元素nums[k]，在剩余的元素中使用双指针i和j分别指向nums[k+1]和数组末尾。 3. 计算当前三个数的和s，如果s与目标值target的差的绝对值小于当前答案ans与target差的绝对值，则更新ans为s。 4. 如果s等于target，直接返回s；如果s大于target，则将右指针j向左移动；如果s小于target，则将左指针i向右移动。 5. 重复步骤3-4，直到左右指针相遇。 6. 返回最接近目标值的和ans。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort() # 对数组进行排序
ans = nums[0] + nums[1] + nums[2] # 初始化答案为前三个数的和
n = len(nums)
for k in range(n): # 固定一个数，索引为k
i = k + 1 # 左指针指向nums[k+1]
j = n - 1 # 右指针指向数组末尾
while i < j:
s = nums[k] + nums[i] + nums[j] # 计算当前三个数的和
if abs(s-target) < abs(ans-target): # 如果当前和更接近目标值，更新答案
ans = s
if s == target: # 如果当前和等于目标值，直接返回
return s
elif s > target: # 如果当前和大于目标值，将右指针向左移动
j -= 1
elif s < target: # 如果当前和小于目标值，将左指针向右移动
i += 1
return ans # 返回最接近目标值的和
排序数组是双指针策略的前提条件，因为只有在有序的数组中，左右指针的移动（左指针向右移增大和，右指针向左移减小和）才有明确的目的和效果。这样可以有效地在数组中寻找和目标值最接近的三个数的组合。
当三个数的和正好等于目标值时，这是最接近目标的结果，因为不能再接近于零的差距。此时，继续寻找其他组合是不必要的，因此可以立即返回当前的和。
将数组的前三个数的和作为初始答案ans是因为经过排序后，这是最快获取初始有效结果的方法。虽然理论上可以选择任何三个数作为初始ans，但这种方法简单且容易实现。其他策略可能包括随机选择或根据特定条件选择，但这些通常不如选择前三个数直接有效。
左右指针的移动基于和与目标值的比较来进行，目的是逐渐减少和与目标值的差距。当和大于目标值时移动右指针，当和小于目标值时移动左指针。这种策略确保了每一次移动都是朝着减少差距的方向进行，最终能找到最接近目标的和。
当前算法的时间复杂度为O(n^2)，主要由排序和双指针操作组成。由于问题本质是寻找最接近的三数之和，这种O(n^2)的复杂度已是相对高效的方法。尽管理论上可以考虑使用更复杂的数据结构或算法来尝试降低复杂度，如使用哈希表或者二分查找，但这些通常会增加实现的复杂性且往往难以显著降低复杂度。
对于短数组，该算法仍然有效，因为它不依赖于数组的长度，只要数组长度至少为三。如果数组中包含重复元素，算法也能正常工作，因为排序和双指针策略能够适应重复值。在处理重复元素时，正确的指针移动仍然可以保证找到最接近的和。