创建网站购买域名要注意什么,wordpress 下载主题,中国建设银行官网站诚聘英才,盐城网站建设效果文章目录题目描述代码 解题思路二刷更新题目描述
主要是解决重复的问题#xff1a;如何去除重复解、在有大量重复解的情况下如何让算法跑得更快
代码 解题思路
先排序#xff0c;按照大小顺序来做。思路#xff1a;固定第一个数#xff0c;用双指针分别代表…
文章目录题目描述代码 解题思路二刷更新题目描述
主要是解决重复的问题如何去除重复解、在有大量重复解的情况下如何让算法跑得更快
代码 解题思路
先排序按照大小顺序来做。思路固定第一个数用双指针分别代表另外两个指针去除重复值对三个数分别进行去除重复解的行为见代码注释第一个数如果num[i] num[i-1]那么num[i-1]肯定已经把num[i]的任务给完成了那么继续进行对num[i]作为第一个数的求解并没有意义而且可能会带来重复解因此跳过第二个数比如说left将要渡过“222”那么用第一个2作为解时剩下的两个2就已经没有意义了于是可以直接跳过后两个2。第三个数和第二个数的原理一样。注意要先取得解再进行跳过重复直接跳重复再取值会出问题或需要更多判断。
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger ans new ArrayListListInteger();int len nums.length;if (len 3) {return ans;}Arrays.sort(nums);if (nums[0] 0 || nums[len - 1] 0) {return ans;}int groupIndex 0;for (int i 0; i len - 2; i) {// 去除第一位重复解if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1, right len - 1;// 双指针法寻找符合条件的情况while(left right){int temp nums[i] nums[left] nums[right];if (temp 0) {ans.add(new ArrayListInteger());ans.get(groupIndex).add(nums[i]);ans.get(groupIndex).add(nums[left]);ans.get(groupIndex).add(nums[right]);groupIndex;// 找到解后去除重复解while(left right nums[left1] nums[left]) left;while (right right nums[right-1] nums[right]) --right;left; right--;}// 大了right往小点走else if (temp 0) {right--;}// 小了left往大点走else {left;}}}return ans;}
}时间复杂度排序O(nlogn) 遍历固定第一解O(n) * 双指针遍历 O(n)算是O(n2n^2n2)空间复杂度O(1)
二刷更新
之前的代码看看注释就好写的有点冗余了不到20行就能解决的事
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger ans new ArrayList();Arrays.sort(nums);for(int i 0; i nums.length - 2; i) {if(i 0 nums[i] nums[i - 1]) continue;int left i 1, right nums.length - 1;while(left right) {int temp nums[i] nums[left] nums[right];if(temp 0) {ListInteger element new ArrayList();element.add(nums[i]);element.add(nums[left]);element.add(nums[right]);ans.add(element);while(left right nums[left 1] nums[left]) left;while(left right nums[right - 1] nums[right]) right--;left; right--;} else if(temp 0) right--;else left;}}return ans;}
}
