---
# System prepended metadata

title: "\n    Leetcode 16. 3Sum Closest\n"
tags: [Array]

---

###### tags: `Array`
<h1>
    Leetcode 16. 3Sum Closest
</h1>
<ol>
    <li>問題描述</li>
    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.<br><br>

Return the sum of the three integers.

You may assume that each input would have exactly one solution.<br><br>
    
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).
    
<li>Input的限制</li>
    <ul>
        <li>3 <= nums.length <= 1000</li>
        <li>-1000 <= nums[i] <= 1000</li>
        <li>-10^4 <= target <= 10^4</li>
    </ul><br>
    
<li>思考流程</li>
    <ul>
        <li>Two Pointers</li>
        這題的目標是，找到 3 數之和最靠近我們的 target 值。在一開始，先對 nums 進行排序，然後加入幾個可以加速的檢測。如果整個 nums 的大小等於 3，那就直接把整個 nums 加起來後回傳；如果 nums[:3] 大於 target，則回傳 sum(nums[:3])；如果 nums[-3:] 小於 target，則回傳 sum(nums[-3:])。<br><br>
        接著我們會遍歷 nums，固定住一個 nums[i]，然後初始化一個 diff 用來記錄 target 與三數相加之差值。如果三數之和與 target 的差值小於 diff，就會更新 diff。
        然後，我們靠 lo & hi 兩個指標，如果三數之和小於 target，則 lo 往右移動；若三數之和大於 target，則 hi 往左邊移動。整個 for loop 跑完後依據最小的 diff 值，回傳 target - diff。
        <br>
        <br>
        會固定住每個 nums[i] 找尋更好的 diff，每個 nums[i] 會利用 two pointers 的方式找到最好的搭配，故 time complexity 是 O(N^2)。根據使用到的 sort 方式不同，會使用到的空間額度也不同，像是 quicksort 會用掉 O(logN)；而 merge sort 會用掉 O(N)，故 space complexity 是 O(logN) ~ O(N)。
        <br>
        <br>
        Time Complexity: O(N^2); Space Complexity: O(logN) ~ O(N)
        <br><br>
    </ul>
<li>測試</li>
    <ul>
        <li>test 1( edge case )</li>
        若 nums 的長度小於 3，則回傳錯誤訊息。
        <li>test 2</li>
        Input: nums = [-1, 5, 3, 1], target = -7<br>
        Output: 3
        <li>test 3</li>
        Input: nums = [-1, 5, 3], target = -5<br>
        Output: 7
        <li>test 4</li>
        Input: nums = [-4, -2, 3, 1, -1], target = 10<br>
        Output: 3
</ol>