3SUM扭曲

Question

我在接受采访时被问到这个问题,并不确定如何回答.这是一个常规的3SUM问题,我们都知道O(n ^ 2)的答案.问题就是这样:你有3个未排序的数组a,b,c.发现三个元件,使得A [1] + 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.

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

我们可以通过保持两个指针a和b来做,最初是在A的最低元素,b是最大的.然后在比较A [a] + B [b]和S之后适当增加或减少b.

对于你的问题,运行O(n)算法n次(所以O(n ^ 2))将S取为全部-C [k].