# [LeetCode 16. 3Sum Closest ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3828/)
### Daily challenge Jul 27, 2021 (MEDIAN)

>Given an array `nums` of n integers 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.

:::info
**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).
:::

:::warning
**Constraints:**
* 3 <= nums.length <= 10^3
* -10^3 <= nums[i] <= 10^3
* -10^4 <= target <= 10^4
:::

---

### Approach 1 : Two Pointer
**`4 ms ( 97.91% )`** **`O(n^2)`**

* **`ans`** 紀錄當前最接近 `target` 的數值。
* `sort nums in non-decreasing order`，
固定 `i` 再透過移動 `left & right` 尋找答案。
>* **`sum == target`** ---> 找到答案，直接回傳 `target` 即可。
>* **`sum < target`** ---> 應該找更大的數值，**`left++`**。
>* **`sum > target`** ---> 應該找更小的數值，**`right--`**。

* 最後比較當前答案是否比較好 **`abs(sum - target) < abs(ans-target)`**，
若較好則存入 **`ans = sum`**。

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