algorithm - 4-SUM の二次アルゴリズム

Question

4-SUM は次のとおりです。

N 個の異なる整数の配列が与えられた場合、a+b+c+d = 0 となる 4 つの整数 a、b、c、d を見つけます。

3-SUM 問題に 2 次アルゴリズムを使用した 3 次アルゴリズムを思い付くことができました。4-SUM をキュービックよりもうまく処理できますか?

Answer 1

はい、できます。数値のすべてのペアを調べて、それらの合計を保存します (また、どの数値がその合計を与えるかを保存します)。その後、各合計について、その否定が合計の中にあるかどうかを確認します。ハッシュを使用すると二次複雑度に到達でき、std::map を使用すると に到達しO(n^2*log(n))ます。

編集：数値が複数回使用されないようにするために、各合計の実際の数値ではなくインデックスを保存することをお勧めします。また、特定の合計が複数のペアで形成される場合があるため、ハッシュ マルチマップを使用する必要があります。合計の数値が異なることを念頭に置いて、X = a1 + a2合計は最大で 1 回使用し-Xて形成される可能性があるため、特定の合計に対して最大 3 つのペアを繰り返して合計として与える必要があります。これは今でも一定です。a1a2X-X

Answer 2

^{この問題には、O(N 2} ) の余分なメモリを使用する O(N ² ) アルゴリズムもあります。

1. すべてのペアごとの合計を O(N ² ) で生成し、ペア (a _i、a _j ) をハッシュ テーブルに格納し、それらの合計の絶対値をハッシュ テーブルのキーとして使用します (a _iと a _jは 2 つの異なるものです)。入力配列の数)

2. テーブルを反復処理し、4 つの特徴的な要素を持つ負と正の両方の合計を持つキーを見つけ、それが答えとして返されます

ハッシュ テーブルを使用したくない場合は別の方法があります。数値は整数であるため、基数ソートなどを使用して、合計リスト内の要素の線形時間ですべての合計のリストをソートできます(合計リストには O(N ² ) 要素があります)。