algorithm - 3SUM 有一个转折

Question

我在面试中被问到这个问题，但不确定如何回答。这是一个常规的 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) 的时间内解决这个问题？

谢谢!

Answer 1

排序 A 和排序 B。

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

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

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