java - 3Sum的两个相似算法之间的区别？

Question

我在 http://www.leetcode.com/onlinejudge 上发现了 3Sum 问题如下所示:

给定一个包含 n 个整数的数组 S，S 中是否存在满足 a + b + c = 0 的元素 a、b、c？找到数组中所有唯一的三元组，其总和为零。

注意: 三元组 (a,b,c) 中的元素必须按非降序排列。 (即 a ≤ b ≤ c) 解决方案集不得包含重复的三元组。

For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 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 的三元组。所以我修改了解决方案并在 for 之后添加了一个条件。

if (num[i] > 0)
    break;

实际上，这应该会减少 for 循环运行的次数，从而减少寻找解决方案所花费的时间。我什至通过添加一个计数器并在每个 if() 递增它来检查这一点.每次 COUNTER因为我的解决方案小于建议解决方案的计数器。

但是，当我在检查页面输入修改后的解决方案时，它要么导致超时错误，要么显示花费的时间比未修改的版本多!我想知道我的修改有什么问题？

Answer 1

我没有发现您的解决方案有任何问题，我在本地尝试了两种解决方案，并在条件运行速度更快的情况下添加了解决方案。我使用 System.nanotime() 检查了时差。由于网络问题，您可能会在解决方案检查页面上遇到超时错误。