2

これは私が解決するように求められたインタビューの質問でした。ソートされていない配列が与えられた場合、配列内の2つの数値とそれらの合計を見つけます。（つまり、1つが他の2つの合計になるように配列内の3つの数値を見つけます。）合計（int k）が与えられたときに2つの数値を見つけることについての質問を見たことがあることに注意してください。ただし、この質問では、配列内の数値と合計を見つける必要があります。O（n）、O（log n）、またはO（nlogn）で解くことができますか

各整数を調べて、それに対して二分探索を行うという標準的な解決策があります。より良い解決策はありますか？

public static void findNumsAndSum(int[] l) {
    // sort the array
    if (l == null || l.length < 2) {
        return;
    }
    BinarySearch bs = new BinarySearch();
    for (int i = 0; i < l.length; i++) {
        for (int j = 1; j < l.length; j++) {
            int sum = l[i] + l[j];
            if (l[l.length - 1] < sum) {
                continue;
            }
            if (bs.binarySearch(l, sum, j + 1, l.length)) {
                System.out.println("Found the sum: " + l[i] + "+" + l[j]
                        + "=" + sum);
            }
        }
    }
}
4

2 に答える 2

4

3SUMこれは、右側にある関連する質問の多くが扱っている標準的な問題に非常に似ています。

あなたの解決策は次のとおりですO(n^2 lg n)。配列の並べ替えに基づくO(n^2)アルゴリズムがあり、このバリアントをわずかに変更するだけで機能します。最もよく知られている下限は次のとおりです (賢ければ、それを使用して比較ソートを実行できるからです)。準二次アルゴリズムまたはより厳密な下限を見つけることができれば、それからいくつかの出版物を得ることができます. :)O(n lg n)

整数を範囲 に制限したい場合は、高速フーリエ変換を使用して時間内[-u, u]に問題を解決できることに注意してください。ただし、問題に合わせて調整する方法はすぐにはわかりません。a + b + c = 0O(n + u lg u)a + b = c

于 2012-07-29T01:01:49.480 に答える
2

次の方法で解決できO(nlog(n))ます。

配列をO(nlog(n))昇順に並べ替えます。配列の左端/右端を指す 2 つのインデックスが必要です。iそれらを と とj呼びましょう。i左のものとj右のものです。

の合計を計算しarray[i] + array[j]ます。

  • この合計が より大きい場合はk、1 減らしjます。
  • この合計が より小さい場合k。1つ増やしiます。

合計が になるまで繰り返しkます。

したがって、このアルゴリズムを使用すると、ソリューションを見つけることができ、O(nlog(n))実装が非常に簡単です

ごめん。私はあなたの投稿を十分に注意深く読んでいないようです;）

于 2012-08-02T23:31:28.813 に答える