题目描述
思路讲解
思路和 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 外层循环。（可以放在循环开头判断。）
代码展示
- class Solution:
- def threeSumClosest(self, nums: List[int], target: int) -> int:
- nums.sort()
- n = len(nums)
- min_diff = inf
- for i in range(n - 2):
- x = nums[i]
- if i and x == nums[i - 1]:
- continue # 优化三
- # 优化一
- s = x + nums[i + 1] + nums[i + 2]
- if s > target: # 后面无论怎么选，选出的三个数的和不会比 s 还小
- if s - target < min_diff:
- ans = s # 由于下一行直接 break，这里无需更新 min_diff
- break
-
- # 优化二
- s = x + nums[-2] + nums[-1]
- if s < target:# x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
- if target - s < min_diff:
- min_diff = target - s
- ans = s
- continue
- # 双指针
- j, k = i + 1, n - 1
- while j < k:
- s = x + nums[j] + nums[k]
- if s == target:
- return s
- if s > target:
- if s - target < min_diff: # s 与 target 更近
- min_diff = s - target
- ans = s
- k -= 1
- else:
- if target - s < min_diff: # s 与 target 更近
- min_diff = target - s
- ans = s
- j += 1
- 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企服之家，中国第一个企服评测及商务社交产业平台。 |
