## [16\. 3Sum Closest](https://leetcode.com/problems/3sum-closest/)

Given an integer array `nums` of length `n` and an integer `target`, find three integers in `nums` such that the sum is closest to `target`.

Return _the sum of the three integers_.

You may assume that each input would have exactly one solution.

**Example 1:**

**Input:** nums = \[-1,2,1,-4\], target = 1
**Output:** 2
**Explanation:** The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

**Example 2:**

**Input:** nums = \[0,0,0\], target = 1
**Output:** 0
**Explanation:** The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

**Constraints:**

- `3 <= nums.length <= 500`
- `-1000 <= nums[i] <= 1000`
- `-104 <= target <= 104`

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int diff = INT_MAX;
        int n = nums.size();
        sort(begin(nums), end(nums));
        for (int i = 0; i < n && diff != 0; ++i) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (abs(target - sum) < abs(diff)) {
                    diff = target - sum;
                }

                if (sum < target) {
                    ++left;
                } else {
                    --right;
                }
            }
        }
        return target - diff;        
    }
};

:::success
- 時間複雜度：$O(N^2)$
- 空間複雜度：$O(\log N)$
:::