微信网站怎么制作,做网站的广告图片,晋城网站建设科技有限公司,嘉兴小程序开发公司15.三数之和
题目
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意#xff1a;答案中不可以包含重复的…15.三数之和
题目
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。
示例 1 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 注意输出的顺序和三元组的顺序并不重要。
示例 2 输入nums [0,1,1] 输出[]
示例 3 输入nums [0,0,0] 输出[[0,0,0]]
思路
暴力循环直接三重循环涵盖所有组合。 但是我们注意到因为题目要求答案不重复那么我们就应该想到排序。此外除开第一层循环剩下的两层循环就是双指针寻找固定值。
java代码
原有代码
报错说内存超出限制。
class Solution {public ListListInteger threeSum(int[] nums) {int lennums.length;ListListIntegerans new ArrayListListInteger();if(len3) return ans;Arrays.sort(nums);int target0;int j0;int klen-1;//第一个数从左到右遍历第二个数从第一个数的右边开始遍历第三个数从数组最右侧开始遍历。for(int i0;ilen;i){//target为第二个数和第三个数的理想目标值。如果此时就已经0了又因为数组是从小到大排序的。那么第二个数和第三个数怎么遍历都不可能加起来0所以退出循环。target0-nums[i];if(target0) break;//因为答案要求不重复那么第一层循环需要跳过重复的元素。while(ilennums[i]nums[i1]) i;System.out.println(target);ji1;klen-1;while(jk){//因为答案要求不重复那么第二层和第三层循环需要跳过重复的元素。while(jknums[k-1]nums[k]) k--;while(jknums[j1]nums[j]) j;//temp为第二个数和第三个数实际的值。int tempnums[j]nums[k];if(temptarget) j;else if(temptarget) k--;else{ListInteger list new ArrayListInteger();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);ans.add(list);j;k--;}} }return ans;}
}问题指出与改进
提交后显示内存超出限制实际上依旧是逻辑有问题。
首先
while(ilennums[i]nums[i1]) i;
\\不应该这么写而应该这么写
if(i0nums[i]nums[i-1]) continue;以下的话能看懂就看看不懂就看样例解释 这两种都会跳过计算重复的i值。但是第一种是先跳过再去计算j和k对应的情况。那么就会导致漏掉j也为重复的i值对应的答案。而第二种是先计算j和k对应的情况下一个i来的时候再看是否与上次的i重复以此判断跳不跳过。
样例解释 nums [-1,0,1,2,-1,-4]排序后为[-4,-1,-1,0,1,2] 第一种碰到第一个-1时就会判断下一位是否也是-1因为下一位确实是-1所以它的i直接从第二个-1开始那么就导致j只能从第二个-1后面的0开始。 而实际上答案包括i为第一个-1j为第二个-1k为2的情况。也就是j与i的值是重复的。所以不能提前跳。
其次
while(jknums[k-1]nums[k]) k--;
while(jknums[j1]nums[j]) j;以下的话能看懂就看看不懂就看样例解释 判断第二重循环和第三重循环时因为不像是i的移动会限制j一样他们跳过重复的值与不跳都是在i和数组结尾之间的范围移动其实就是第二重循环和第三重循环是并行的另一种体现所以这里可以用while循环。 但是这个while循环不应该在答案加入j和k之前就判断而是应该在加入答案后再判断。因为会漏掉j和k相等的答案情况。
样例解释 nums[-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0] 排序后就是 -5 -5 -4 -4 -4 -2 -2 -2 0 0 0 1 1 3 4 4 结果应该输出[[-5,1,4],[-4,0,4],[-4,1,3],[-2,-2,4],[-2,1,1],[0,0,0]] 但是如果while循环在答案加入j和k之前就判断那么当k移动到第二个1的时候它就会自动跳到第一个1那么答案的[-2,1,1]就会丢失。j的移动同理。
改进后的代码
class Solution {public ListListInteger threeSum(int[] nums) {int lennums.length;ListListIntegerans new ArrayListListInteger();if(len3) return ans;Arrays.sort(nums);int target0;int j0;int klen-1;//第一个数从左到右遍历第二个数从第一个数的右边开始遍历第三个数从数组最右侧开始遍历。for(int i0;ilen-1;i){//target为第二个数和第三个数的理想目标值。如果此时就已经0了又因为数组是从小到大排序的。那么第二个数和第三个数怎么遍历都不可能加起来0所以退出循环。target0-nums[i];if(target0) break;//因为答案要求不重复那么第一层循环需要跳过重复的元素。// 注意出现了nums[i-1]那么要加上i0的判断if(i0nums[i]nums[i-1]) continue;ji1;klen-1;while(jk){//temp为第二个数和第三个数实际的值。int tempnums[j]nums[k];if(temptarget) j;else if(temptarget) k--;else{//因为答案要求不重复那么第二层和第三层循环需要跳过重复的元素。ans.add(Arrays.asList(nums[i], nums[j],nums[k]));while(jknums[k-1]nums[k]) k--;while(jknums[j1]nums[j]) j;k--;j;}} }return ans;}
}其他知识点ans.add(Arrays.asList(nums[i], nums[j],nums[k]));
