7

面试时被问到这个问题，不知道怎么回答。这是一个常规的 3SUM 问题，我们都知道 O(n^2) 的答案。问题是这样的：你有 3 个未排序的数组 a、b、c。找到三个元素，使得 a[i] + b[j] + c[k] = 0。在这种情况下，您不允许使用散列，并且解决方案必须 <= O(n^2)

这是我的答案，是的，不幸的是，这仍然是 O(n^3)

public static void get3Sum(int[] a, int[] b, int[] c) {
    int i = 0, j = 0, k = 0, lengthOfArrayA = a.length, lengthOfArrayB = b.length, lengthOfArrayC = c.length;

    for (i = 0; i < lengthOfArrayA; i++) {
        j = k = 0;
        while (j < lengthOfArrayB) {
            if (k >= lengthOfArrayC) {
                j++;
                continue;
            } else if (a[i] + b[j] + c[k] == 0) {
                // found it: so print
                System.out.println(a[i] + " " + b[j] + " " + c[k]);
                k++;
                if (j > lengthOfArrayB - 1)
                    break;

            } else {
                k++;
                if (k >= lengthOfArrayC) {
                    j++;
                    k = 0;
                }

            }
        }
    }
}

有人有什么绝妙的想法可以在小于或等于 O(N^2) 的时间内解决这个问题吗？

谢谢！

4

1 回答 1

8

排序 A 和排序 B。

一旦我们在 O(n) 时间内排序，给定一个 S，我们就可以解决找到 i,j 的问题，使得 A[i] + B[j] = S。

我们可以通过维护两个指针 a 和 b 来做到这一点，a 最初位于 A 的最低元素，b 位于最大元素。然后在将 A[a] + B[b] 与 S 进行比较之后，适当地增加或减少 b。

对于您的问题，通过将 S 全部设为 -C[k] 来运行 O(n) 算法 n 次（因此 O(n^2)）。

于 2012-08-26T03:03:32.000 回答