每天一道leetcode15-三數之和
- 2019 年 10 月 4 日
- 筆記
昨天的題解
題目
每天一道leetcode15-三數之和 分類：數組 中文鏈接： https://leetcode-cn.com/problems/3sum/submissions/ 英文鏈接 https://leetcode.com/problems/3sum/submissions/
題目詳述
給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重複的三元組。 注意：答案中不可以包含重複的三元組。 例如, 給定數組 nums = [-1, 0, 1, 2, -1, -4]， 滿足要求的三元組集合為： [ [-1, 0, 1], [-1, -1, 2] ]
題目詳解
思路
- 這個題目和昨天的挺像的，就在昨天的程式碼改了改就AC了
- 先sort一下array，為啥要sort呢，因為要用到two pointers 來遍歷找兩數之和，只有在從小到大排序之後的結果上，才能根據情況移動left 和right。
- 首先是如果數組只有3個數字，那麼直接返回這三個數字之和；（最少三個數）
- 當確定好了第一個數字後，就在剩下的array里找兩數之和，在加上第一個數字，得到tempSum,比較這個tempSum是不是等於0，如果是0，則把這個結果保存下來（這裡注意先把結果存到hashSet裡面，去重）
- 之後如果tempSum與0不相等 利用two pointers 特性， 如果tempSum 比0 小的話，說明我們需要更大的sum，所以要讓left++以便得到更大的sum。 如果tempSum 比0 大的話，我們就需要更小的sum，所以right--。
class Solution { public List<List<Integer>> threeSum(int[] nums) { HashSet<List<Integer>> set = new HashSet<>(); List<List<Integer>> result = new ArrayList<>(); int target = 0; if(nums.length == 3) { if(nums[0] + nums[1] + nums[2] == 0) { List<Integer> temp = new ArrayList<>(); temp.add(nums[0]); temp.add(nums[1]); temp.add(nums[2]); result.add(temp); return result; } return result; } Arrays.sort(nums); 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]; if(tempSum == 0 ) { List<Integer> temp = new ArrayList<>(); temp.add(nums[one]); temp.add(nums[left]); temp.add(nums[right]); set.add(temp); } if(tempSum < target) { left++; }else{ right--; } } } for(List<Integer> t : set) { result.add(t); } return result; } } 程式碼講解
- 6-18行就是如果數組長度是3，那麼直接判斷數組和是不是0，如果是0則返回這個，不是返回kong
- 19行對nums進行排序
- 20-42行中第20行就是從首先確定一個數，22-23行就是從確定的數的下一個left+1到數組的長度-1這個範圍內找出這兩個數。
- 26-34行就是判斷這三個數的和tempSum是不是0，如果是0那麼就填入到hashset中
- 35-40行就是之後如果tempSum與0不相等 利用two pointers 特性， 如果tempSum 比0 小的話，說明我們需要更大的sum，所以要讓left++以便得到更大的sum。 如果tempSum 比0 大的話，我們就需要更小的sum，所以right--。
- 43-46行 遍歷這個set然後加入到List中，把它返回。