1 中文题目

给一个长度为 n 的整数数组 nums 和 一个目标值 target。请从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。

示例 ：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

• $3\le nums.length\le 1000$
• $-1000\le nums[i]\le 1000$
• $-10^4\le target\le 10^4$

---

2 求解方法1：二分查找法

2.1 思路说明

排序保证有序性，固定两个数，用二分查找找第三个数，维护一个全局最小差值，记录最接近的和。

具体思路

• 预处理阶段：
  • 对数组进行排序，保证有序性
  • 初始化最接近和为前三个数的和
• 外层固定处理：
  • 第一层循环固定第一个数nums[i]
  • 第二层循环固定第二个数nums[j]
  • 计算当前已固定两数之和sum_two = nums[i] + nums[j]
  • 计算需要寻找的目标值need = target - sum_two
• 二分查找阶段：
  • 在区间[j+1, n-1]内寻找第三个数
  • 比较中间位置的值nums[mid]与need的关系
  • 根据nums[mid]与need的大小关系调整区间
  • 每次更新时计算当前三数之和与target的差值
• 更新策略：
  • 维护全局最小差值min_diff
  • 维护最接近的和closest_sum
  • 当找到完全相等的和时直接返回
  • 当找到更小的差值时更新结果

2.2 Python代码

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:"""使用二分查找求解最接近的三数之和:param nums: 输入数组:param target: 目标值:return: 最接近目标值的三数之和"""# 数组排序nums.sort()n = len(nums)# 初始化最接近的和closest_sum = nums[0] + nums[1] + nums[2]# 特判：如果target小于最小三数和或大于最大三数和min_sum = nums[0] + nums[1] + nums[2]max_sum = nums[-1] + nums[-2] + nums[-3]if target <= min_sum:return min_sumif target >= max_sum:return max_sum# 固定第一个数for i in range(n-2):# 去重if i > 0 and nums[i] == nums[i-1]:continue# 固定第二个数for j in range(i+1, n-1):# 去重if j > i+1 and nums[j] == nums[j-1]:continue# 二分查找第三个数# 计算需要找的目标值need = target - nums[i] - nums[j]# 在[j+1, n-1]范围内二分查找left = j + 1right = n - 1# 如果范围内只有一个数，直接判断if left == right:curr_sum = nums[i] + nums[j] + nums[left]if abs(curr_sum - target) < abs(closest_sum - target):closest_sum = curr_sumcontinue# 二分查找过程while left < right - 1:  # 保留两个相邻的数mid = left + (right - left) // 2curr_sum = nums[i] + nums[j] + nums[mid]# 更新最接近的和if abs(curr_sum - target) < abs(closest_sum - target):closest_sum = curr_sum# 根据大小关系调整区间if curr_sum == target:return targetelif curr_sum > target:right = midelse:left = mid# 检查区间内剩余的数# 检查left位置curr_sum = nums[i] + nums[j] + nums[left]if abs(curr_sum - target) < abs(closest_sum - target):closest_sum = curr_sum# 检查right位置curr_sum = nums[i] + nums[j] + nums[right]if abs(curr_sum - target) < abs(closest_sum - target):closest_sum = curr_sumreturn closest_sum

2.3 复杂度分析

• 时间复杂度：O(n²logn)
  • 排序：O(nlogn)
  • 第一层循环：O(n)
  • 第二层循环：O(n)
  • 内层二分查找：O(logn)
• 空间复杂度：O(logn)或O(n)
  • 排序空间：O(logn)或O(n)
  • 其他变量：O(1)

---

3 求解方法2：排序 + 双指针法

3.1 思路说明

先将数组排序，以便使用双指针。固定一个数，用双指针在剩余部分寻找最接近的两个数。通过比较三数之和与目标值的差值，不断更新最接近的结果

详细算法步骤：

• 首先对数组排序，便于使用双指针和去重
• 固定第一个数nums[i]，然后使用双指针(left, right)在剩余数组中寻找最接近的两个数
• 在遍历过程中：
  • 计算当前三数之和sum = nums[i] + nums[left] + nums[right]
  • 比较sum与target的差值，更新最接近的结果
  • 如果sum > target，right左移
  • 如果sum < target，left右移
  • 如果sum == target，直接返回target

优化策略：

• 去重：跳过重复的第一个数
• 剪枝：根据排序后的特性提前结束

3.2 Python代码

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:"""最接近的三数之和:param nums: 输入数组:param target: 目标值:return: 最接近目标值的三数之和"""n = len(nums)# 先对数组排序,便于使用双指针和剪枝nums.sort()# 初始化最接近和为前三个数的和closest_sum = nums[0] + nums[1] + nums[2]# 优化1:先判断边界情况# 如果target小于数组中最小的三数之和min_sum = nums[0] + nums[1] + nums[2]if target <= min_sum:return min_sum# 如果target大于数组中最大的三数之和max_sum = nums[-1] + nums[-2] + nums[-3]if target >= max_sum:return max_sum# 固定第一个数,遍历数组for i in range(n-2):# 去重:跳过重复的第一个数if i > 0 and nums[i] == nums[i-1]:continue# 优化2:当前最小和已经大于target# 由于数组已排序,后面的和只会更大,可以提前结束curr_min = nums[i] + nums[i+1] + nums[i+2]if curr_min > target:# 更新closest_sum(如果当前的最小和更接近target)if abs(curr_min - target) < abs(closest_sum - target):closest_sum = curr_minbreak# 优化3:当前最大和小于target# 说明以当前数字为第一个数时,找不到比当前closest_sum更接近的和curr_max = nums[i] + nums[-1] + nums[-2]if curr_max < target:# 更新closest_sum(如果当前的最大和更接近target)if abs(curr_max - target) < abs(closest_sum - target):closest_sum = curr_maxcontinue# 使用双指针在剩余数组中寻找最接近的两个数left = i + 1  # 左指针right = n - 1  # 右指针while left < right:# 计算当前三数之和curr_sum = nums[i] + nums[left] + nums[right]# 如果恰好等于target,直接返回if curr_sum == target:return target# 更新最接近的和if abs(curr_sum - target) < abs(closest_sum - target):closest_sum = curr_sum# 根据curr_sum与target的关系移动指针if curr_sum > target:# 和太大,右指针左移right -= 1else:# 和太小,左指针右移left += 1return closest_sum

3.3 复杂度分析

• 时间复杂度：O(n²)
  • 排序：O(nlogn)
  • 主循环：O(n)
  • 双指针循环：O(n)
• 空间复杂度分析：O(logn)或O(n)
  • 排序空间：O(logn)或O(n)
  • 其他变量：O(1)

---

4 题目总结

题目难度：中等
数据结构：数组
应用算法：双指针、分治法