首页 > 代码库 > leet_3Sum
leet_3Sum
一.问题
二.解决方法
1.这个题类似于在一个给定的数组中找出所有满足给定数值的整数对,先看一下这个问题
这个问题的简单的解题思路就是移动两个指针,便利数组,具体代码:
1 for(int i=0,j=num.length-1;i<j;) 2 { 3 //Move the j-pointer to the left till the sum <=c 4 if(num[i]+num[j]>0) 5 { 6 j--; 7 continue; 8 } 9 if(num[i]+num[j]<0) 10 { 11 i++; 12 continue; 13 } 14 if(num[i]+num[j]==0) 15 System.out.println(num[i]+" "+num[j]); 16 i++; 17 }
这样会输出重复的答案
2.过滤掉重复的结果
1 for(int i=0,j=num.length-1;i<j;) 2 { 3 //Move the j-pointer to the left till the sum <=c 4 if(num[i]+num[j]>0) 5 { 6 j--; 7 continue; 8 } 9 if(num[i]+num[j]<0) 10 { 11 i++; 12 continue; 13 } 14 if(num[i]+num[j]==0) 15 System.out.println(num[i]+" "+num[j]); 16 while(num[i] == num[i+1]) i++; 17 i++; 18 }
3.这道题和sum2问题的本质一样,我们可以设置两层循环,外层循环固定一个给定的target,来找另外两个满足sum是-target的数组
1 //排序 2 Arrays.sort(num); 3 for(int i=0;i<num.length;i++) 4 { 5 //不能重复(外层) 6 if((i>0)&&(num[i]==num[i-1]))continue; 7 //This loop is essentially the same as findpairs() above. 8 for(int j=i+1,k=num.length-1;j<k;) 9 { 10 if(num[i]+num[j]+num[k]>0) 11 { 12 k--; 13 continue; 14 } 15 if(num[i]+num[j]+num[k]<0){ 16 j++; 17 continue; 18 } 19 if(num[i]+num[j]+num[k]==0) 20 { 21 res.add(Arrays.asList(num[i], num[j], num[k])); 22 //不重复(内层) 23 while (j < k && num[j] == num[k]) j++; 24 while (j < k && num[j] == num[k]) k--; 25 j++; k--; 26 continue; 27 } 28 } 29 }
总结:在解决类似在数组中找给定和数对,给定和的三元组,一般都可以通过多层向少层转 最后注意:要怎样过滤掉重复的结果集
leet_3Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。