Leetcode 259. 3Sum Smaller

###### tags: `Array` <h1> Leetcode 259. 3Sum Smaller </h1> <ol> <li>問題描述</li> Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target. Example 1: Input: nums = [-2,0,1,3], target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1], [-2,0,3] Example 2: Input: nums = [], target = 0 Output: 0 Example 3: Input: nums = [0], target = 0 Output: 0 <li>Input的限制</li> <ul> <li>0 <= nums.length <= 3500</li> <li>-100 <= nums[i] <= 100</li> <li>-100 <= target <= 100</li> </ul> <li>思考流程</li> <ul> <li>Two Pointers</li> 這題主要想找到總共有幾組 triplets，其和小於 target 值。在正式開始 two pointer 的機制前，會先檢查 nums 的大小是否小於 3，如果是的話就直接回傳 0。然後我們會檢查 nums 前三個元素和是否大於等於 target，如果是的話，則直接回傳 0。 然後我們會遍歷 nums 一次，每次迭代固定一個 nums[i]，然後 lo 指向 nums[i+1]，hi 指向 nums[len(nums) - 1]。當 total = nums[i] + nums[lo] + nums[hi] 小於 target 的話，代表 hi 向左移動到 lo 隔壁為止的所有組合的 triplets 都會小於 target，所以 res = res + (hi - lo)，然後 lo = lo + 1；如果大於 target 的話，則 hi = hi - 1。最後回傳 res。 我們固定住每個 nums[i] 後，利用 two pointers 的方式找到每個小於 target 的 triplets，故 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</li> Input: nums = [1, 3], target = 5 Output: 0 <li>test 2</li> Input: nums = [-1, 5, 3, 1], target = 2 Output: 3 </ol>