java – 3Sum的两个相似算法之间的区别?
发布时间:2020-12-15 02:34:25 所属栏目:Java 来源:网络整理
导读:我在 http://www.leetcode.com/onlinejudge上发现了3Sum问题,如下所示: 给定n个整数的数组S,S中是否有元素a,b,c,使得a b c = 0?找到数组中所有唯一的三元组,它们的总和为零. 注意: ????三元组(a,c)中的元素必须是非降序. (即a≤b≤c) ????解决方案集不得
我在
http://www.leetcode.com/onlinejudge上发现了3Sum问题,如下所示:
给定n个整数的数组S,S中是否有元素a,b,c,使得a b c = 0?找到数组中所有唯一的三元组,它们的总和为零. 注意: For example,given array S = {-1 0 1 2 -1 -4},A solution set is: (-1,1) (-1,-1,2) 我浏览了网站,发现了这个建议的解决方案: public ArrayList<ArrayList<Integer>> threeSum(int[] num) { Arrays.sort(num); HashSet<ArrayList<Integer>> lstSoln = new HashSet<ArrayList<Integer>>(); ArrayList<Integer> tempArr = null; for (int i = 0; i < num.length; i++) { int j = i + 1; int k = num.length - 1; while (j < k) { int sum3 = num[i] + num[j] + num[k]; if (sum3 < 0) { j++; } else if (sum3 > 0) { k--; } else { tempArr = new ArrayList<Integer>(); Collections.addAll(tempArr,num[i],num[j],num[k]); lstSoln.add(tempArr); j++; k--; } } } return new ArrayList<ArrayList<Integer>>(lstSoln); } 如您所见,这将获取每个数字,然后在当前索引之后使用两个数字.所以,很明显,一旦达到第一个正数,我们只是做无用的循环,我们不会发现任何三元组加到0.所以我修改了解决方案并添加了一个条件 if (num[i] > 0) break; 实际上,这应该降低for循环运行的次数,从而减少找到解决方案所花费的时间.我甚至通过添加计数器并在每个if()处递增它来检查.每次我的解决方案的COUNTER小于建议解决方案的计数器. 但是,当我在检查页面输入我的修改后的解决方案时,它会导致超时错误或显示的时间超过未修改的版本!我想知道我的修改有什么问题? 解决方法
我没有看到你的解决方案有什么问题,我尝试了我的本地解决方案和添加条件运行速度更快的解决方案.我使用System.nanotime()检查了时差.由于网络问题,您可能在解决方案检查页面上面临超时错误.
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |