n^2 * log（n）時間に4つの数字を持つ3sumの変形？

Question

私はアルゴリズムコースのプロジェクトに取り組んでいます。私は完全に邪魔しています。代入は、O（n^2 * log（n））時間内のi + j = k + lの配列の4つの数のすべての集合を見つけることです。

これは3sumの問題と似ていますが、i + j + k = 0の配列のすべてのセットを見つける必要があります。私たちは、この問題の解を、2（n^2時間）のすべての固有の対を反復し、ソートされた配列のバイナリ検索を使用してO（n^2 * log問題（log（n）time）を満たす値を見つける。

しかし、この時点で4つの数字の問題がどのように解決されたかはわかりません。私は複雑さのlog（n）がバイナリ検索から来ていることを安全に推測していると思います。これは最後のものに使用します。しかし、それはn^2時間で3のすべての可能な組み合わせを反復しなければならないことを意味します。これは可能ではないと思います。

私は自分の仕事をしてくれる人を探しているわけではありませんが、これがどのように解決できるかを知っていれば、正しい方向に優しいタップを与えることができます。ありがとう。

編集：ソートを使用して解決する必要があることに注意してください。私がそれをしたら、ハッシングを使って速くする別の実装を書かなければなりませんが、自分でそれをうまくやることができると思います。私は最初にソートすることでどのように問題を解決できるかを理解する必要があります。

Answer 1

合計とペアのソートされたリストを保持します。例えば、リスト

[1, 2, 4, 8, 16, 32, 9, 82] 

我々は1+9 = 2+8

がリストに最大2つの数値を特定する識別したいと思うでしょう、O **（N）**を与えられました。この場合、それらは（82,32）であり、114の合計です。114の位置に配列pair_sumを割り当てます。すべての場所をヌルポインタに設定します。

ここで、i、jペアのリストを繰り返します。各ペアについて、インデックスi + jにタプル値として2つの数値を挿入します。いくつかのインデックスで衝突が発生すると、2番目のペア合計が見つかりました。

私はこれをいくつかの非常に擬似的なコードで概説します。あなたの好きな実装言語に翻訳することができます。有界で

バンク= [1、2、4、8、16、32、9、82] サイズ=長さ（バンク）

// Find the two largest numbers and allocate the array ... 
pair_sum = array[114], initialize to all nulls 

for lo in 0:size-1 
    for hi in lo+1:size 
     sum = bank[lo] + bank[hi] 
     if pair_sum[sum] 
      // There is already a pair with that sum 
      print pair_sum[sum], "and", bank[lo], bank[hi] 
     else 
      // Record new sum pair 
      pair_sum[sum] = tuple(bank[lo], bank[hi]) 

これはO（N^2）、スペースは配列値に依存します。あなたは、実際的な理由のための指標としての和を使用することを許可されていない場合は

、私はあなたがあなたのログ（N）コンポーネントを与えて、バイナリ検索や挿入にこれを適応させることができると思います。