相向双指针-16. 最接近的三数之和

题目描述

思路讲解

思路和 15. 三数之和 类似，排序后，枚举 nums 作为第一个数，那么问题变成找到另外两个数，使得这三个数的和与 target 最接近，这同样可以用双指针解决。
设 s=nums+nums[j]+nums[k]，为了判断 s 是不是与 target 最近的数，我们还必要用一个变量 minDiff 维护 ∣s−target∣ 的最小值。分类讨论：

• 如果 s=target，那么答案就是 s，直接返回 s。
  
• 如果 s>target，那么如果s−target<minDiff，说明找到了一个与 target 更近的数，更新 minDiff 为 s−target，更新答案为s。然后和三数之和一样，把 k 减一。
  
• 否则 s<target，那么如果 target−s<minDiff，说明找到了一个与target 更近的数，更新 minDiff 为 target−s，更新答案为 s。然后和三数之和一样，把 j 加一。
  

除此以外，另有以下几个优化：

• 设 s=nums+nums[i+1]+nums[i+2]。如果s>target，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，以是不会找到比 s 更优的答案了。以是只要s>target，就可以直接 break 外层循环了。在 break 前判断 s 是否离 target 更近，如果更近，那么更新答案为s。
  
• 设 s=nums+nums[n−2]+nums[n−1]。如果 s<target，由于数组已经排序，nums加上后面任意两个数都不超过 s，以是下面的双指针就不必要跑了，无法找到比 s 更优的答案。但是后面另有更大的nums，可能找到一个离 target 更近的三数之和，以是还必要继续枚举，continue 外层循环。在 continue前判断 s 是否离 target 更近，如果更近，那么更新答案为 s，更新 minDiff 为 target−s。
  
• 如果 i>0 且 nums=nums[i−1]，那么 nums和后面数字相加的结果，一定在之前算出过，以是无需跑下面的双指针，直接 continue 外层循环。（可以放在循环开头判断。）
  

代码展示

1. class Solution:
2.     def threeSumClosest(self, nums: List[int], target: int) -> int:
3.         nums.sort()
4.         n = len(nums)
5.         min_diff = inf
6.         for i in range(n - 2):
7.             x = nums[i]
8.             if i and x == nums[i - 1]:
9.                 continue # 优化三
10.             # 优化一
11.             s = x + nums[i + 1] + nums[i + 2]
12.             if s > target: # 后面无论怎么选，选出的三个数的和不会比 s 还小
13.                 if s - target < min_diff:
14.                     ans = s # 由于下一行直接 break，这里无需更新 min_diff
15.                 break
16.             
17.             # 优化二
18.             s = x + nums[-2] + nums[-1]
19.             if s < target:# x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
20.                 if target - s < min_diff:
21.                     min_diff = target - s
22.                     ans = s
23.                 continue
24.             # 双指针
25.             j, k = i + 1, n - 1
26.             while j < k:
27.                 s = x + nums[j] + nums[k]
28.                 if s == target:
29.                     return s
30.                 if s > target:
31.                     if s - target < min_diff: # s 与 target 更近
32.                         min_diff = s - target
33.                         ans = s
34.                     k -= 1
35.                 else:
36.                     if target - s < min_diff: # s 与 target 更近
37.                         min_diff = target - s
38.                         ans = s
39.                     j += 1
40.         return ans

复制代码

复杂度分析

• 时间复杂度：O(                                                   n                               2                                            n^2                     n2)，其中 n 为 nums 的长度。排序 O(nlogn)。外层循环枚举第一个数，然后O(n)双指针。以是总的时间复杂度为 O(                                                   n                               2                                            n^2                     n2)。
  
• 空间复杂度：O(1)。返回值不计入，忽略排序的栈开销。
  

相关标签

• 数组
  
• 双指针
  
• 排序
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。