【LeetCode笔记】15.三数之和（JAVA、双指针）

题目描述

• 主要是解决重复的问题&＃xff1a;如何去除重复解、在有大量重复解的情况下如何让算法跑得更快
  

代码 & 解题思路

• 先排序&＃xff0c;按照大小顺序来做。
• 思路&＃xff1a;固定第一个数&＃xff0c;用双指针分别代表另外两个指针
• 去除重复值&＃xff1a;对三个数&＃xff0c;分别进行去除重复解的行为&＃xff08;见代码注释&＃xff09;&＃xff1a;
• 第一个数&＃xff1a;如果num[i] &＃61;&＃61; num[i-1]&＃xff0c;那么num[i-1]肯定已经把num[i]的任务给完成了&＃xff0c;那么继续进行对num[i]作为第一个数的求解并没有意义&＃xff0c;而且可能会带来重复解&＃xff0c;因此跳过
• 第二个数&＃xff1a;比如说left将要渡过“222”&＃xff0c;那么用第一个2作为解时&＃xff0c;剩下的两个2就已经没有意义了&＃xff0c;于是可以直接跳过后两个2。
• 第三个数&＃xff1a;和第二个数的原理一样。
• 注意&＃xff1a;要先取得解&＃xff0c;再进行跳过重复&＃xff0c;直接跳重复&＃xff0c;再取值会出问题&＃xff0c;或需要更多判断。

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans &＃61; new ArrayList<List<Integer>>();int len &＃61; nums.length;if (len < 3) {return ans;}Arrays.sort(nums);if (nums[0] > 0 || nums[len - 1] < 0) {return ans;}int groupIndex &＃61; 0;for (int i &＃61; 0; i < len - 2; i&＃43;&＃43;) {// 去除第一位重复解if (i > 0 && nums[i] &＃61;&＃61; nums[i - 1]) {continue;}int left &＃61; i &＃43; 1, right &＃61; len - 1;// 双指针法寻找符合条件的情况while(left < right){int temp &＃61; nums[i] &＃43; nums[left] &＃43; nums[right];if (temp &＃61;&＃61; 0) {ans.add(new ArrayList<Integer>());ans.get(groupIndex).add(nums[i]);ans.get(groupIndex).add(nums[left]);ans.get(groupIndex).add(nums[right]);groupIndex&＃43;&＃43;;// 找到解后&＃xff0c;去除重复解while(left < right && nums[left&＃43;1] &＃61;&＃61; nums[left]) &＃43;&＃43;left;while (right < right && nums[right-1] &＃61;&＃61; nums[right]) --right;left&＃43;&＃43;; right--;}// 大了&＃xff0c;right往小点走else if (temp > 0) {right--;}// 小了&＃xff0c;left往大点走else {left&＃43;&＃43;;}}}return ans;}
}


• 时间复杂度&＃xff1a;排序O(nlogn) &＃43; 遍历固定第一解O(n) * 双指针遍历 O(n)&＃xff0c;算是O(n2n^2n2)
• 空间复杂度&＃xff1a;O(1)

二刷更新

• 之前的代码看看注释就好&＃xff0c;写的有点冗余了&＃xff0c;不到20行就能解决的事

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans &＃61; new ArrayList<>();Arrays.sort(nums);for(int i &＃61; 0; i < nums.length - 2; i&＃43;&＃43;) {if(i > 0 && nums[i] &＃61;&＃61; nums[i - 1]) continue;int left &＃61; i &＃43; 1, right &＃61; nums.length - 1;while(left < right) {int temp &＃61; nums[i] &＃43; nums[left] &＃43; nums[right];if(temp &＃61;&＃61; 0) {List<Integer> element &＃61; new ArrayList<>();element.add(nums[i]);element.add(nums[left]);element.add(nums[right]);ans.add(element);while(left < right && nums[left &＃43; 1] &＃61;&＃61; nums[left]) left&＃43;&＃43;;while(left < right && nums[right - 1] &＃61;&＃61; nums[right]) right--;left&＃43;&＃43;; right--;} else if(temp > 0) right--;else left&＃43;&＃43;;}}return ans;}
}