Leetcode 16. 3Sum Closest

###### 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. 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). <li>Input的限制</li> <ul> <li>3 <= nums.length <= 1000</li> <li>-1000 <= nums[i] <= 1000</li> <li>-10^4 <= target <= 10^4</li> </ul> <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:])。 接著我們會遍歷 nums，固定住一個 nums[i]，然後初始化一個 diff 用來記錄 target 與三數相加之差值。如果三數之和與 target 的差值小於 diff，就會更新 diff。然後，我們靠 lo & hi 兩個指標，如果三數之和小於 target，則 lo 往右移動；若三數之和大於 target，則 hi 往左邊移動。整個 for loop 跑完後依據最小的 diff 值，回傳 target - diff。 會固定住每個 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)。 Time Complexity: O(N^2); Space Complexity: O(logN) ~ O(N) </ul> <li>測試</li> <ul> <li>test 1( edge case )</li> 若 nums 的長度小於 3，則回傳錯誤訊息。 <li>test 2</li> Input: nums = [-1, 5, 3, 1], target = -7 Output: 3 <li>test 3</li> Input: nums = [-1, 5, 3], target = -5 Output: 7 <li>test 4</li> Input: nums = [-4, -2, 3, 1, -1], target = 10 Output: 3 </ol>