題目描述
給定一個長度為 n 的整數數組 nums 和一個整數target，在 nums 中找到三個整數，使得總和最接近target。傳回三個整數的總和。可以假設每個輸入都有一個解決方案。
- 範例 1：
Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: 最接近目標值 1 的三元組為 [-1, 2, 1]，其和為 2。 - 範例 2：
Input: nums = [0, 0, 0], target = 1
Output: 0
Explanation: 三數之和為 0，最接近目標值 1。
解題思路
本題的目標是找到和最接近 target 的三元組，類似於 3Sum 問題，但這次我們不需要找出所有符合條件的三元組，而是找到最接近的和。
- 暴力解法：枚舉所有三元組，計算它們的和並更新最接近目標的結果。
- 排序 + 雙指針：將陣列排序後，利用雙指針的優化來有效縮小搜尋範圍。
解法 1：暴力解法
思路
- 使用三層迴圈，枚舉所有可能的三元組，計算每個三元組的和與
target的差值。 - 逐一比較並更新最接近的和。
實現 (Python)
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
closest_sum = float('inf') # 初始化為無限大
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
current_sum = nums[i] + nums[j] + nums[k]
# 如果目前的和比之前更接近目標，則更新結果
if abs(current_sum - target) < abs(closest_sum - target):
closest_sum = current_sum
return closest_sum
時間與空間複雜度
- 時間複雜度：O(n³)，三層迴圈遍歷所有可能的三元組。
- 空間複雜度：O(1)，除了變數儲存外，無額外空間使用。
解法 2：排序 + 雙指針
思路
- 排序陣列：先將陣列排序，這樣可以方便使用雙指針技巧。
- 固定一個數字，然後在剩下的陣列中尋找最接近的兩數和：
- 遍歷陣列中的每個數字作為固定值 nums[i]。
- 使用雙指針在剩下的陣列中尋找最接近 target - nums[i] 的兩數和。
- 更新結果：比較每組三元組的和與目標值的接近程度，並更新結果。
實現 (Python)
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort() # 將陣列排序
closest_sum = float('inf') # 初始化為無限大
n = len(nums)
for i in range(n):
left, right = i + 1, n - 1 # 雙指針
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
# 更新最接近的和
if abs(current_sum - target) < abs(closest_sum - target):
closest_sum = current_sum
# 根據 current_sum 與 target 的大小調整指針
if current_sum < target:
left += 1
elif current_sum > target:
right -= 1
else:
return current_sum # 如果剛好等於 target，直接返回
return closest_sum
時間與空間複雜度
- 時間複雜度：O(n²)
- 排序的時間複雜度為 O(n log n)，雙指針遍歷的時間複雜度為 O(n²)，總計 O(n²)。
- 空間複雜度：O(1)
- 除了排序外，僅需使用額外變數儲存指針與結果。
總結
排序 + 雙指針 是本題的最佳解法，因為它在時間效率和實現簡潔性之間達到了很好的平衡。希望這篇詳細的教學能幫助你理解並解決這個問題！
