每天一道leetcode16-最接近的三數之和
- 2019 年 10 月 4 日
- 筆記
以下是昨天的題解
題目
每天一道leetcode16-最接近的三數之和 分類：數組 中文鏈接： https://leetcode-cn.com/problems/3sum-closest/description/ 英文鏈接 https://leetcode.com/problems/3sum-closest/description/
題目詳述
給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。 例如，給定數組 nums = [-1，2，1，-4], 和 target = 1. 與 target 最接近的三個數的和為 2. (-1 + 2 + 1 = 2).
題目詳解
思路
- 先sort一下array，為啥要sort呢，因為要用到two pointers 來遍歷找兩數之和，只有在從小到大排序之後的結果上，才能根據情況移動left 和right。
- 首先是如果數組只有3個數字，那麼直接返回這三個數字之和；（最少三個數）
- 當確定好了第一個數字後，就在剩下的array里找兩數之和，在加上第一個數字，用這個tempSum減去target 來得到tempCha；（tempCha就是臨時的一個差值）
- 比較tempCha與之前保留的cha的值大小，如果比cha小，那麼說明此刻的tempCha就有可能是最小的差，記錄下來這個時候的tempCha和這個時候的可能是最後返回結果的三數之和
- 利用two pointers 特性， 如果tempSum 比target 小的話，說明我們需要更大的sum，所以要讓left++以便得到更大的sum。 如果tempSum 比target 大的話，我們就需要更小的sum，所以right–。如果相等的話，直接return 就可以了。因為都相等了，那麼差值就等於0，不會有差值再小的了。
代碼
class Solution { public int threeSumClosest(int[] nums, int target) { if(nums.length == 3) return nums[0] + nums[1] + nums[2]; Arrays.sort(nums); int result = 0; int cha = Integer.MAX_VALUE; int tempCha = 0 ; for(int one=0;one < nums.length-2;one++) { int left = one + 1; int right = nums.length - 1; while(left < right) { int tempSum = nums[one] + nums[left] + nums[right]; tempCha = Math.abs(tempSum - target); if(tempCha < cha) { cha = tempCha; result = tempSum; } if(tempSum == target) { return target; } if(tempSum < target) { left++; }else{ right--; } } } return result; } }
代碼講解
- 3-4行 三個數直接返回這三個數之和
- 9行的意思是固定下來一個數，然後從剩下的數組中進行雙指針操作
- 11-12行，每次都是從9行固定的數開始，從數組末尾，這兩個端點進行雙指針逼近
- 15-21行就是如果和tempSum與target的差值tempCha比之前的cha還要小，那麼說明是可能的最小的cha，也就是可能的最接近target的和，把這些中結果保留下來
- 22-31行就是 利用two pointers 特性， 如果tempSum 比target 小的話，說明我們需要更大的sum，所以要讓left++以便得到更大的sum。 如果tempSum 比target 大的話，我們就需要更小的sum，所以right–。如果相等的話，直接return 就可以了。因為都相等了，那麼差值就等於0，不會有差值再小的了。
經驗教訓
見注釋
class Solution { public int threeSumClosest(int[] nums, int target) { if(nums.length == 3) return nums[0] + nums[1] + nums[2]; Arrays.sort(nums); int result = 0; int one = 0; int tempSum = nums[one] + nums[1] + nums[nums.length-1]; int cha = Integer.MAX_VALUE; int left = 1; int right = nums.length - 1; int tempCha = 0 ; for(one=0;one < nums.length-2;one++) { left = one + 1; right = nums.length - 1; while(left < right) { tempSum = nums[one] + nums[left] + nums[right]; tempCha = Math.abs(tempSum - target); if(tempCha <= cha) { cha = tempCha; result = tempSum;//這裡的潛在的最後的正確結果沒注意保存 }else{ break;//這裡使用了一個break,我以為tempCha大於cha這一層循環就不用了，但是沒準往中間逼近的時候和還更小了呢，這裡想當然了 } if(tempSum == target) { return target; } if(tempSum < target) { left++; }else{ right--; } } } return result; } }
