LeetCode【0016】最靠近的三数之和

1 中文题目

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

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

复制代码

1. 输入：nums = [0,0,0], target = 1
2. 输出：0
3. 解释：与 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[j]
    
  • 盘算当前已固定两数之和sum_two = nums + nums[j]
    
  • 盘算必要探求的目标值need = target - sum_two
    
  
  
• 二分查找阶段：
  
  
  
  • 在区间[j+1, n-1]内探求第三个数
    
  • 比较中间位置的值nums[mid]与need的关系
    
  • 根据nums[mid]与need的巨细关系调整区间
    
  • 每次更新时盘算当前三数之和与target的差值
    
  
  
• 更新战略：
  
  
  
  • 维护全局最小差值min_diff
    
  • 维护最靠近的和closest_sum
    
  • 当找到完全相等的和时直接返回
    
  • 当找到更小的差值时更新效果
    
  
  

2.2 Python代码

1. class Solution:
2.     def threeSumClosest(self, nums: List[int], target: int) -> int:
3.         """
4.         使用二分查找求解最接近的三数之和
5.         :param nums: 输入数组
6.         :param target: 目标值
7.         :return: 最接近目标值的三数之和
8.         """
9.         # 数组排序
10.         nums.sort()
11.         n = len(nums)
12.         # 初始化最接近的和
13.         closest_sum = nums[0] + nums[1] + nums[2]
14.         
15.         # 特判：如果target小于最小三数和或大于最大三数和
16.         min_sum = nums[0] + nums[1] + nums[2]
17.         max_sum = nums[-1] + nums[-2] + nums[-3]
18.         if target <= min_sum:
19.             return min_sum
20.         if target >= max_sum:
21.             return max_sum
22.             
23.         # 固定第一个数
24.         for i in range(n-2):
25.             # 去重
26.             if i > 0 and nums[i] == nums[i-1]:
27.                 continue
28.                
29.             # 固定第二个数
30.             for j in range(i+1, n-1):
31.                 # 去重
32.                 if j > i+1 and nums[j] == nums[j-1]:
33.                     continue
34.                     
35.                 # 二分查找第三个数
36.                 # 计算需要找的目标值
37.                 need = target - nums[i] - nums[j]
38.                
39.                 # 在[j+1, n-1]范围内二分查找
40.                 left = j + 1
41.                 right = n - 1
42.                
43.                 # 如果范围内只有一个数，直接判断
44.                 if left == right:
45.                     curr_sum = nums[i] + nums[j] + nums[left]
46.                     if abs(curr_sum - target) < abs(closest_sum - target):
47.                         closest_sum = curr_sum
48.                     continue
49.                     
50.                 # 二分查找过程
51.                 while left < right - 1:  # 保留两个相邻的数
52.                     mid = left + (right - left) // 2
53.                     curr_sum = nums[i] + nums[j] + nums[mid]
54.                     
55.                     # 更新最接近的和
56.                     if abs(curr_sum - target) < abs(closest_sum - target):
57.                         closest_sum = curr_sum
58.                         
59.                     # 根据大小关系调整区间
60.                     if curr_sum == target:
61.                         return target
62.                     elif curr_sum > target:
63.                         right = mid
64.                     else:
65.                         left = mid
66.                         
67.                 # 检查区间内剩余的数
68.                 # 检查left位置
69.                 curr_sum = nums[i] + nums[j] + nums[left]
70.                 if abs(curr_sum - target) < abs(closest_sum - target):
71.                     closest_sum = curr_sum
72.                     
73.                 # 检查right位置
74.                 curr_sum = nums[i] + nums[j] + nums[right]
75.                 if abs(curr_sum - target) < abs(closest_sum - target):
76.                     closest_sum = curr_sum
77.                     
78.         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[left] + nums[right]
    
  • 比较sum与target的差值，更新最靠近的效果
    
  • 如果sum > target，right左移
    
  • 如果sum < target，left右移
    
  • 如果sum == target，直接返回target
    
  
  

优化战略：

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

3.2 Python代码

1. class Solution:
2.     def threeSumClosest(self, nums: List[int], target: int) -> int:
3.         """
4.         最接近的三数之和
5.         :param nums: 输入数组
6.         :param target: 目标值
7.         :return: 最接近目标值的三数之和
8.         """
9.         n = len(nums)
10.         # 先对数组排序,便于使用双指针和剪枝
11.         nums.sort()
12.         # 初始化最接近和为前三个数的和
13.         closest_sum = nums[0] + nums[1] + nums[2]
14.         
15.         # 优化1:先判断边界情况
16.         # 如果target小于数组中最小的三数之和
17.         min_sum = nums[0] + nums[1] + nums[2]
18.         if target <= min_sum:
19.             return min_sum
20.             
21.         # 如果target大于数组中最大的三数之和
22.         max_sum = nums[-1] + nums[-2] + nums[-3]
23.         if target >= max_sum:
24.             return max_sum
25.             
26.         # 固定第一个数,遍历数组
27.         for i in range(n-2):
28.             # 去重:跳过重复的第一个数
29.             if i > 0 and nums[i] == nums[i-1]:
30.                 continue
31.                
32.             # 优化2:当前最小和已经大于target
33.             # 由于数组已排序,后面的和只会更大,可以提前结束
34.             curr_min = nums[i] + nums[i+1] + nums[i+2]
35.             if curr_min > target:
36.                 # 更新closest_sum(如果当前的最小和更接近target)
37.                 if abs(curr_min - target) < abs(closest_sum - target):
38.                     closest_sum = curr_min
39.                 break
40.                
41.             # 优化3:当前最大和小于target
42.             # 说明以当前数字为第一个数时,找不到比当前closest_sum更接近的和
43.             curr_max = nums[i] + nums[-1] + nums[-2]
44.             if curr_max < target:
45.                 # 更新closest_sum(如果当前的最大和更接近target)
46.                 if abs(curr_max - target) < abs(closest_sum - target):
47.                     closest_sum = curr_max
48.                 continue
49.                
50.             # 使用双指针在剩余数组中寻找最接近的两个数
51.             left = i + 1  # 左指针
52.             right = n - 1  # 右指针
53.             
54.             while left < right:
55.                 # 计算当前三数之和
56.                 curr_sum = nums[i] + nums[left] + nums[right]
57.                
58.                 # 如果恰好等于target,直接返回
59.                 if curr_sum == target:
60.                     return target
61.                     
62.                 # 更新最接近的和
63.                 if abs(curr_sum - target) < abs(closest_sum - target):
64.                     closest_sum = curr_sum
65.                     
66.                 # 根据curr_sum与target的关系移动指针
67.                 if curr_sum > target:
68.                     # 和太大,右指针左移
69.                     right -= 1
70.                 else:
71.                     # 和太小,左指针右移
72.                     left += 1
73.                     
74.         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企服之家，中国第一个企服评测及商务社交产业平台。