題目描述:給定整數陣列 nums 和整數 target,從陣列中找出三個數,使其總和最接近 target,回傳該總和。題目保證恰好有一個答案。
解題思路:先將陣列排序,讓雙指針技巧得以發揮。固定第一個數(外層迴圈指針 i),剩下兩個數用左指針 l = i+1 和右指針 r = n-1 從兩端向中間夾逼。每次計算三數之和 sum,若 |sum - target| 比目前最佳更小,就更新答案。接著根據 sum 與 target 的大小關係移動指針:sum < target 時左指針右移(讓 sum 變大);sum > target 時右指針左移(讓 sum 變小);若 sum == target 則直接回傳,無需繼續。
時間複雜度:O(n²) — 排序 O(n log n),外層迴圈 O(n),內層雙指針 O(n),合計 O(n²) 主導。
空間複雜度:O(1) — 僅使用常數個輔助變數(排序為原地),不計入輸出。
1. Sort nums in ascending order.
2. Initialize closest = nums[0] + nums[1] + nums[2].
3. For i from 0 to n-3:
a. Set l = i+1, r = n-1.
b. While l < r:
- Compute sum = nums[i] + nums[l] + nums[r].
- If |sum - target| < |closest - target|: update closest = sum.
- If sum < target: l++ (increase sum).
- Else if sum > target: r-- (decrease sum).
- Else: return sum immediately (exact match).
4. Return closest.方法一:暴力三重迴圈(Brute Force) — 枚舉所有三元組,追蹤最小差值,時間複雜度 O(n³),空間 O(1)。n 較大時效率不佳。
方法二:排序 + 雙指針(最優解) — 如本題解,時間 O(n²)、空間 O(1)。排序後利用單調性讓雙指針在線性時間完成每次固定元素後的搜尋。
方法三:排序 + 二分搜尋 — 固定兩個數後,對第三個數使用二分搜尋找最接近 target - nums[i] - nums[l] 的值,時間複雜度同為 O(n² log n),實作略複雜,不如雙指針直觀。