三数之和（去重）

科技前沿 • 2025-02-11 19:13 • 阅读 54

大家好，我是讯享网，很高兴认识大家。

一，排列数组

看见这道题，立马出现的思路是3重循环遍历，但仔细一想会发现这样会有很多问题，比如当数组中有相同的元素时，如果第一重循环的数等于之前第二或三重循环的数并且第二或三重循环的数等于第一重循环的数时就会出现重复，所以不妨先把数列按重小到大排列保证第一个数<=第二个数<=第三个数

二，优化

当我们排列了数组之后其实可以不用第三次循环了，因为第三个数一定是大于第二个数的，所以直接在第二个数后面的数中查找第三个数即可

三，大概思路

第一步，先一层循环确定第一个数

第二步，第二层循环找到第二和第三个数使得第二个数加第三个数等于第一个数的相反数，这时我们可以利用双指针，第二个数为左指针第三个数为右指针，当两数之和大于第一个数的相反数的时候右指针左移，当相等的时候即为答案，当小于的时候左指针右移。

class Solution { public List<List<Integer>> threeSum(int[] nums) { //第一步：将数组由小到大排列 sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); for(int i=0;i<nums.length;i++){ if(i>0 && nums[i]==nums[i-1]){continue;} for(int j=i+1;j<nums.length;j++){ if(j>i+1 && nums[j]>0 && nums[j]==nums[j-1]){continue;} for(int k=nums.length-1;k>j;k--){ if(nums[i]+nums[j]+nums[k]==0){ List<Integer> num=new ArrayList<Integer>(); num.add(nums[i]); num.add(nums[j]); num.add(nums[k]); ans.add(num); } } } } return ans; } public int[] sort(int[] nums){ for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] < nums[i]) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } } return nums; } }

讯享网

用了for循环，出现了重复问题

改用while循环得解

讯享网class Solution { public List<List<Integer>> threeSum(int[] nums) { //第一步：将数组由小到大排列 sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); for(int i=0;i<nums.length;i++){ int k=nums.length-1; if(i>0 && nums[i]==nums[i-1]){continue;} for(int j=i+1;j<nums.length;j++){ if(j>i+1 && nums[j]==nums[j-1]){continue;} while (j < k && nums[j] + nums[k] > -nums[i]) { --k; } // 如果指针重合，随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if (j == k) { break; } if(nums[i]+nums[j]+nums[k]==0){ List<Integer> num=new ArrayList<Integer>(); num.add(nums[i]); num.add(nums[j]); num.add(nums[k]); ans.add(num); } } } return ans; } public int[] sort(int[] nums){ for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] < nums[i]) { int temp = nums[j]; nums[j] = nums[i]; nums[i] = temp; } } } return nums; } }

三数之和（去重）

一，排列数组

二，优化

三，大概思路

相关推荐