📘 題目敘述
給定一個整數陣列 nums，以及一個整數 target。
請找出三個索引互不相同的數，使它們的總和最接近 target。
最後回傳這三個數的總和。
題目保證每組輸入都剛好有唯一答案。
條件限制
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-10^4 <= target <= 10^4
🧠 解題思路
我這題的想法和 3Sum 很像，先排序，再固定一個數，剩下兩個數用 two pointers 去找。
因為排序之後，如果目前三數總和太大，我就可以把右指標往左移；如果總和太小，我就把左指標往右移。
這樣可以在每個固定的 i 下，有效率地找出更接近 target 的三數總和。
我在過程中用 ans 記錄目前最接近 target 的答案。
每次算出新的三數總和 sum，就比較：
- 目前答案和
target的距離 - 新總和和
target的距離
如果新的比較近，就更新 ans。
所有變數
ans：目前找到最接近target的三數總和n：陣列長度l：左指標r：右指標sum：目前這組三個數的總和
🪜 主要流程步驟
1. 先初始化答案，並把陣列排序
我先把答案 ans 設成前三個數的總和：
int ans = nums[0] + nums[1] + nums[2];
這樣後面在比較時，一定已經有一個合法初始答案可以參考。
接著我把整個陣列排序：
sort(nums.begin(), nums.end());
排序之後，才能利用 two pointers 的性質來調整總和大小。
2. 固定第一個數，剩下兩個數用 two pointers 尋找
我用外層迴圈固定第一個位置 i：
for (int i = 0; i < n - 2; i++) {
因為總共要選三個數，所以 i 最多只需要跑到 n - 3。
接著在每個 i 底下，我設：
l = i + 1r = n - 1
也就是在 i 右邊那段區間裡，用左右指標去找另外兩個數。
3. 計算目前三數總和，必要時更新答案
在 l < r 的時候，我先算出目前這組三數總和：
int sum = nums[i] + nums[l] + nums[r];
然後比較它和 target 的距離，看看有沒有比目前的 ans 更接近：
if (abs(ans - target) > abs(sum - target)) {
ans = sum;
}
如果新的 sum 更接近 target，我就把答案更新成 sum。
4. 根據目前總和和 target 的關係移動指標
更新完答案後，我就看目前的 sum 和 target 的大小關係。
如果：
if (sum > target) {
r--;
}
表示現在總和太大了。 因為陣列已經排序好，所以我要讓總和變小，就把右指標左移。
否則：
else {
l++;
}
表示目前總和小於等於 target。
這時要讓總和變大，就把左指標右移。
這樣每次都能朝著更接近 target 的方向繼續找。
5. 全部掃完後回傳最接近的總和
當所有 i 都處理完之後，ans 裡面記錄的就是整個陣列中最接近 target 的三數總和，直接回傳即可。
⏱️ 複雜度
設 n = nums.length。
- 時間複雜度：
O(n^2)排序是O(n log n)，外層固定一個數之後，內層 two pointers 總共是O(n)，所以整體是O(n^2)。 - 空間複雜度：
O(1)如果不計排序所需的額外空間，這份寫法只用了固定數量的變數。
💻 程式碼實作
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int ans = nums[0] + nums[1] + nums[2];
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; i++) {
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (abs(ans - target) > abs(sum - target)) {
ans = sum;
}
if (sum > target) {
r--;
} else {
l++;
}
}
}
return ans;
}
};
🔗 題目連結
https://leetcode.com/problems/3sum-closest/