7

面接でこの質問をされたのですが、どう答えたらいいのかわかりませんでした。これは通常の 3SUM 問題で、O(n^2) の答えは誰もが知っています。質問は次のようになります: 3 つのソートされていない配列 a、b、c があります。a[i] + b[j] + c[k] = 0 となる 3 つの要素を見つけます。このシナリオではハッシュを使用できず、解は <= 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。

Sが与えられた場合、O（n）時間でソートすると、A [i] + B [j] = Sとなるようにi、jを見つける問題を解決できます。

これは、最初はAの最も低い要素に、bは最大の2つのポインターaとbを維持することによって実行できます。次に、A [a] + B [b]をSと比較した後、aを適切にインクリメントまたはbをデクリメントします。

問題については、Sをすべて-C [k]として、O（n）アルゴリズムをn回（つまりO（n ^ 2））実行します。

于 2012-08-26T03:03:32.000 に答える