題目描述

思路講解

思路和 15. 三數之和 類似，排序后，枚舉 nums[i] 作為第一個數，那么問題變成找到另外兩個數，使得這三個數的和與 target 最接近，這同樣可以用雙指針解決。

設 s=nums[i]+nums[j]+nums[k]，為了判斷 s 是不是與 target 最近的數，我們還需要用一個變量 minDiff 維護 ∣s?target∣ 的最小值。分類討論：

1. 如果 s=target，那么答案就是 s，直接返回 s。
2. 如果 s>target，那么如果s?target<minDiff，說明找到了一個與 target 更近的數，更新 minDiff 為 s?target，更新答案為s。然后和三數之和一樣，把 k 減一。
3. 否則 s<target，那么如果 target?s<minDiff，說明找到了一個與target 更近的數，更新 minDiff 為 target?s，更新答案為 s。然后和三數之和一樣，把 j 加一。

除此以外，還有以下幾個優化：

1. 設 s=nums[i]+nums[i+1]+nums[i+2]。如果s>target，由于數組已經排序，后面無論怎么選，選出的三個數的和不會比 s 還小，所以不會找到比 s 更優的答案了。所以只要s>target，就可以直接 break 外層循環了。在 break 前判斷 s 是否離 target 更近，如果更近，那么更新答案為s。
2. 設 s=nums[i]+nums[n?2]+nums[n?1]。如果 s<target，由于數組已經排序，nums[i]加上后面任意兩個數都不超過 s，所以下面的雙指針就不需要跑了，無法找到比 s 更優的答案。但是后面還有更大的nums[i]，可能找到一個離 target 更近的三數之和，所以還需要繼續枚舉，continue 外層循環。在 continue前判斷 s 是否離 target 更近，如果更近，那么更新答案為 s，更新 minDiff 為 target?s。
3. 如果 i>0 且 nums[i]=nums[i?1]，那么 nums[i]和后面數字相加的結果，必然在之前算出過，所以無需跑下面的雙指針，直接 continue 外層循環。（可以放在循環開頭判斷。）

代碼展示

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)min_diff = inffor 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_diffbreak# 優化二s = x + nums[-2] + nums[-1]if s < target:# x 加上后面任意兩個數都不超過 s，所以下面的雙指針就不需要跑了if target - s < min_diff:min_diff = target - sans = scontinue# 雙指針j, k = i + 1, n - 1while j < k:s = x + nums[j] + nums[k]if s == target:return sif s > target:if s - target < min_diff: # s 與 target 更近min_diff = s - targetans = sk -= 1else:if target - s < min_diff: # s 與 target 更近min_diff = target - sans = sj += 1return ans

復雜度分析

1. 時間復雜度：O($n^2$)，其中 n 為 nums 的長度。排序 O(nlogn)。外層循環枚舉第一個數，然后O(n)雙指針。所以總的時間復雜度為 O($n^2$)。
2. 空間復雜度：O(1)。返回值不計入，忽略排序的棧開銷。

相關標簽

• 數組
• 雙指針
• 排序