LeetCode【0016】最接近的三数之和
本文目录
- 1 中文题目
- 2 求解方法1：二分查找法
- 2.1 思路说明
- 2.2 Python代码
- 2.3 复杂度分析
- 3 求解方法2：排序 + 双指针法
- 3.1 思路说明
- 3.2 Python代码
- 3.3 复杂度分析
- 4 题目总结
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 ≤ n u m s . l e n g t h ≤ 1000 3 \leq nums.length \leq 1000 3≤nums.length≤1000
- − 1000 ≤ n u m s [ i ] ≤ 1000 -1000 \leq nums[i] \leq 1000 −1000≤nums[i]≤1000
- − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4 \leq target \leq 10^4 −104≤target≤104
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_sum
if 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 + 1
right = 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_sum
continue
# 二分查找过程
while left < right - 1: # 保留两个相邻的数
mid = left + (right - left) // 2
curr_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 target
elif curr_sum > target:
right = mid
else:
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_sum
return 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_min
break
# 优化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_max
continue
# 使用双指针在剩余数组中寻找最接近的两个数
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 -= 1
else:
# 和太小,左指针右移
left += 1
return closest_sum
3.3 复杂度分析
- 时间复杂度：O(n²)
- 排序：O(nlogn)
- 主循环：O(n)
- 双指针循环：O(n)
- 空间复杂度分析：O(logn)或O(n)
- 排序空间：O(logn)或O(n)
- 其他变量：O(1)
4 题目总结
题目难度：中等
数据结构：数组
应用算法：双指针、分治法