每天一道leetcode18-四數之和
- 2019 年 10 月 4 日
- 筆記
昨天的題解
題目
每天一道leetcode18- 四數之和 分類：雙指針 中文鏈接： https://leetcode-cn.com/problems/4sum/description/ 英文鏈接 https://leetcode.com/problems/4sum/description/
題目詳述
給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。 注意： 答案中不可以包含重複的四元組。 示例： 給定數組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 滿足要求的四元組集合為： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
題目詳解
思路
- 這個題目和昨天的挺像的，就在昨天的程式碼改了改就AC了
- 先sort一下array，為啥要sort呢，因為要用到two pointers 來遍歷找兩數之和，只有在從小到大排序之後的結果上，才能根據情況移動left 和right。
- 首先是如果數組只有4個數字，直接判斷4個數的和是不是target；（最少4個數）
- 當確定好了第一個數字和第二個數字以後，如何確定？一個從開頭開始，begin,是外層循環，一個從末尾往前遍歷，end,是內層循環(要注意，必須間隔兩個數，因為要取4個數)
- 就在剩下的array里找找兩個數，left從begin+1開始，right從end-1開始往前遍歷，取4個數的和得到tempSum,比較這個tempSum是不是等於target，如果是target，則把這個結果保存下來（這裡注意先把結果存到hashSet裡面，去重）
- 之後如果tempSum與target不相等 利用two pointers 特性， 如果tempSum 比target 小的話，說明我們需要更大的sum，所以要讓left++以便得到更大的sum。 如果tempSum 比target 大的話，我們就需要更小的sum，所以right–。
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { HashSet<List<Integer>> set = new HashSet<>(); List<List<Integer>> result = new ArrayList<>(); if(nums.length == 4) { if(nums[0] + nums[1] + nums[2] + nums[3] == target) { List<Integer> temp = new ArrayList<>(); temp.add(nums[0]); temp.add(nums[1]); temp.add(nums[2]); temp.add(nums[3]); result.add(temp); return result; } return result; } Arrays.sort(nums); for(int begin = 0;begin < nums.length-3;begin++) { for(int end = nums.length-1;end - begin > 2;end--) { int left = begin + 1; int right = end - 1; while(left < right) { int tempSum = nums[begin] + nums[end] + nums[left] + nums[right]; if(tempSum == target) { List<Integer> temp = new ArrayList<>(); temp.add(nums[begin]); temp.add(nums[left]); temp.add(nums[right]); temp.add(nums[end]); set.add(temp); left++; }else if(tempSum < target) left++; else right--; } } } for(List<Integer> t: set) result.add(t); return result; } }
程式碼講解
- 5-18行就是如果數組長度是4，那麼直接判斷數組和是不是target，如果是target則返回這個，不是返回空
- 19行對nums進行排序
- 20-22行就是先確定好兩個數，一個begin一個end,注意間隔end-begin>2的哦~
- 26-37行就是判斷這4個數的和tempSum是不是target，如果是target那麼就填入到hashset中
- 38-41行就是之後如果tempSum與target不相等 利用two pointers 特性， 如果tempSum 比target小的話，說明我們需要更大的sum，所以要讓left++以便得到更大的sum。 如果tempSum 比0 大的話，我們就需要更小的sum，所以right–。
- 45-47行 遍歷這個set然後加入到List中，把它返回。
