15. 三數之和
給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復的三元組，
注意：答案中不可以包含重復的三元組，
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2：
輸入：nums = []
輸出：[]
示例 3：
輸入：nums = [0]
輸出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
解題思路
要求三元組不同， 想到先給陣列排序
確定第一個值，想到后兩個值相加為第一個值得相反數，一個增加，另一個必然減小
采用雙指標，第二次和第三次回圈一同進行
每次回圈的值大于初始值，并且等于上一次的值，跳出回圈 來保證值唯一
1 class Solution { 2 public List<List<Integer>> threeSum(int[] nums) { 3 Arrays.sort(nums); 4 List<List<Integer>> res = new ArrayList<>(); 5 for (int k = 0; k < nums.length - 2; k++) { 6 if (nums[k] > 0) { 7 break; 8 } 9 if (k > 0 && nums[k - 1] == nums[k]) { 10 continue; 11 } 12 int i = k + 1; 13 int j = nums.length - 1; 14 while (i < j) { 15 int sum = nums[k] + nums[i] + nums[j]; 16 if (sum == 0) { 17 res.add(new ArrayList<>(Arrays.asList(nums[k], nums[i], nums[j]))); 18 while (i < j && nums[i] == nums[++i]); 19 while (i < j && nums[j] == nums[--j]); 20 }else if (sum < 0) { 21 while (i < j && nums[i] == nums[++i]); 22 }else { 23 while (i < j && nums[j] == nums[--j]); 24 } 25 } 26 } 27 return res; 28 } 29 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500117.html
標籤：其他
上一篇：實驗設計