LeetCode【0016】最靠近的三数之和
1 中文题目给一个长度为 n 的整数数组 nums 和 一个目标值 target。请从 nums 中选出三个整数，使它们的和与 target 最靠近。返回这三个数的和。假定每组输入只存在恰好一个解。
示例 ：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
输入：nums = , 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 \leq 1000 −1000≤nums≤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
[*]第二层循环固定第二个数nums
[*]盘算当前已固定两数之和sum_two = nums + nums
[*]盘算必要探求的目标值need = target - sum_two
[*]二分查找阶段：
[*]在区间内探求第三个数
[*]比较中间位置的值nums与need的关系
[*]根据nums与need的巨细关系调整区间
[*]每次更新时盘算当前三数之和与target的差值
[*]更新战略：
[*]维护全局最小差值min_diff
[*]维护最靠近的和closest_sum
[*]当找到完全相等的和时直接返回
[*]当找到更小的差值时更新效果
2.2 Python代码
class Solution:
def threeSumClosest(self, nums: List, target: int) -> int:
"""
使用二分查找求解最接近的三数之和
:param nums: 输入数组
:param target: 目标值
:return: 最接近目标值的三数之和
"""
# 数组排序
nums.sort()
n = len(nums)
# 初始化最接近的和
closest_sum = nums + nums + nums
# 特判：如果target小于最小三数和或大于最大三数和
min_sum = nums + nums + nums
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 == nums:
continue
# 固定第二个数
for j in range(i+1, n-1):
# 去重
if j > i+1 and nums == nums:
continue
# 二分查找第三个数
# 计算需要找的目标值
need = target - nums - nums
# 在范围内二分查找
left = j + 1
right = n - 1
# 如果范围内只有一个数，直接判断
if left == right:
curr_sum = nums + nums + nums
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 + nums + nums
# 更新最接近的和
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 + nums + nums
if abs(curr_sum - target) < abs(closest_sum - target):
closest_sum = curr_sum
# 检查right位置
curr_sum = nums + nums + nums
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，然后使用双指针(left, right)在剩余数组中探求最靠近的两个数
[*]在遍历过程中：
[*]盘算当前三数之和sum = nums + nums + nums
[*]比较sum与target的差值，更新最靠近的效果
[*]如果sum > target，right左移
[*]如果sum < target，left右移
[*]如果sum == target，直接返回target
优化战略：
[*]去重：跳过重复的第一个数
[*]剪枝：根据排序后的特性提前结束
3.2 Python代码
class Solution:
def threeSumClosest(self, nums: List, target: int) -> int:
"""
最接近的三数之和
:param nums: 输入数组
:param target: 目标值
:return: 最接近目标值的三数之和
"""
n = len(nums)
# 先对数组排序,便于使用双指针和剪枝
nums.sort()
# 初始化最接近和为前三个数的和
closest_sum = nums + nums + nums
# 优化1:先判断边界情况
# 如果target小于数组中最小的三数之和
min_sum = nums + nums + nums
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 == nums:
continue
# 优化2:当前最小和已经大于target
# 由于数组已排序,后面的和只会更大,可以提前结束
curr_min = nums + nums + nums
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 + 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 + nums + nums
# 如果恰好等于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 题目总结
题目难度：中等
数据结构：数组
应用算法：双指针、分治法
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]