描述
給一個包含 n 個整數的數組 S, 找到和與給定整數 target 最接近的三元組，傳回這三個數的和。
隻需要傳回三元組之和，無需傳回三元組本身
線上評測位址：
領扣題庫官網樣例1
輸入:[2,7,11,15],3
輸出:20
解釋:
2+7+11=20 樣例2
輸入:[-1,2,1,-4],1
輸出:2
解釋:
-1+2+1=2 解法思路
- 本題是 57. 三數之和 的擴充問題，不再要求恰好相等，而是找與target最接近的三數之和。
-
本題需要計算三數之和，如果用暴力枚舉，時間複雜度會是O(n3)O(n3)。我們這裡采用雙指針的方法，來降低時間複雜度。首先将數組排序，然後固定一個數numbersi上用雙指針來找與target最接近的三數之和nearest。
算法流程
- 第一步，對數組進行排序。隻有将數組轉化為有序數組，我們才友善移動雙指針。
- 第二步，在數組numbers中周遊，每次固定numbers[i]作為第一個數
- 建立雙指針left和right，初始化分别指向i + 1和len(numbers) - 1
- 求出此時的三數之和curr，如果curr和target恰好相等，我們可以直接傳回target。
- 比較curr和nearest誰距離target更近，如果是curr，那麼将nearest更新為target
- 判斷curr和target的大小關系，如果curr > target，那麼right左移；反之，left右移。繼續第二步的過程，直到left >= right。
-
此外，當數組中有重複元素時，為了避免重複運算，在代碼中添加了三處剪枝操作。當指針指向新的位置和舊的位置的值相等時，我們繼續移動指針。
算法複雜度
- 時間複雜度
- 數組排序的時間複雜度為O(nlogn)O(nlogn)
- 周遊過程，固定值為 n 次，雙指針為 n 次，時間複雜度為 O(n2))O(n2))
- 總時間複雜度：O(nlogn)+O(n2)=O(n2)O(nlogn)+O(n2)=O(n2)
- 空間複雜度為O（1），隻需要常量空間。
class Solution: """ @param numbers: Give an array numbers of n integer @param target: An integer @return: return the sum of the three integers, the sum closest target. """ def threeSumClosest(self, numbers, target): nearest = float('inf') # step1: 首先對數組進行排序 numbers = sorted(numbers) # step2: 周遊 for i in range(len(numbers) - 2): # 剪枝1 if (i > 0 and numbers[i] == numbers[i - 1]): continue # 定義雙指針 left = i + 1 right = len(numbers) - 1 # 雙指針相向而行 while (left < right): # 此時的三數之和 curr = numbers[left] + numbers[right] + numbers[i] # 和恰好為target if curr == target: return target # 更新 nearest if abs(curr - target) < abs(nearest - target): nearest = curr # 移動雙指針 if curr > target: right -= 1 # 剪枝2 while (right >= 0 and numbers[right] == numbers[right + 1]): right -= 1 else: left += 1 # 剪枝3 while (left < len(numbers) and numbers[left] == numbers[left - 1]): left += 1 return nearest
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)