題目網址：https://leetcode.cn/problems/3sum-closest/

題意：給一長度為 n 的整數 array nums 和一整數 target, 從 nums 選出三個整數, 使其 sum 最接近 target, 返回這三個數之 sum。

假設每個輸入恰只存在一個解。

Solution：

想法：利用 Two Pointers

  • 首先, 將 nums 由小到大做排序, 用 res 來記錄當前最接近 target 之 sum
  • 用 i 遍歷 [0 , n], 每一次 i 遍歷一元素
    • 使用 Two pointer 尋找：left = i + 1, right = n - 1, 並用 sum 紀錄當前三數之和
    • 若 sum 比 res 還更接近 target, 則 res = sum
    • 否則, 代表 sum 比 res 離 target 更遠, 則可細分成兩種情形：
      • sum < target：left + 1
      • sum ≥ target：right - 1
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        const int n = nums.size();
        int res = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n; ++i) {
            int left = i + 1, right = n - 1;

            while (left < right) {
                const int sum = nums[i] + nums[left] + nums[right];

                if (abs(sum - target) < abs(res - target)) {
                    res = sum;
                } else if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }

        return res;
    }
};
  • time：$O(n^2)$ ➔ $O(n \cdot log(n)) + O(n^2)$
    • $O(n \cdot log(n))$：排序 nums
    • $O(n^2)$：for loop 需 $O(n)$, 其中每一個元素用 two pointer 遍歷剩餘元素需 $O(n)$
  • space：$O(1)$ ➔ 撇除要返回的 res, 只需常數空間