两种类似的3Sum算法有何不同？

Question

我在http://www.leetcode.com/onlinejudge上发现了关于3Sum问题，其问题描述如下：

给定一个由n个整数组成的数组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都小于建议解决方案的计数器。

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

- inquizitive

---

你的解决方案是否可以在被判定为超时之前执行更多的测试用例，从而显示更高的价值？你的确做得更好。另外，需要注意的是，如果我们不考虑32位整数限制，3SUM的下限为O(n^2)。 - Haozhun

Answer 1

我认为你的解决方案没有任何问题，我在本地尝试了两种解决方案，加入if条件的那个运行速度更快。我使用System.nanotime()检查了时间差异。你可能会在检查解决方案的页面上遇到超时错误，因为存在网络问题。

- coder

---

起初我也是这么想的，但后来我用修改过和未修改过的版本进行了多次检查，结果差不多。根据他们的说法，未修改的那个运行得更快。即使在我的电脑上使用 System.nanoTime()，很明显我的代码应该更快。 - inquizitive