2つの異なる配列のすべての要素のペアを素早く見つける方法

Question

最近、私はこのプログラミング上の問題にぶつかり、複雑さを少なくすることはできませんでした（現在のコードはO（n^2）で実行されます）。

本質的に、正と負の整数の4つの異なるリスト（私はpython btwを使用しています）を持っています。これらのリストはそれぞれ1000個の整数を持ち、これらの整数-25000〜25000の範囲である。今、これらのリストのそれぞれから、a、b、c、dという整数を選択するとします。私はこれらのa、b、c、dがa + b = - （c + d）となるような素早い方法を知りたい。

現在、私の方法では、a、b、c、dのすべての可能な組み合わせを反復してから、セット内の要素（a + b） d）。もちろん、これはO（n^2）時間で実行されるため実用的ではありません。

誰かがもっと効率的な方法（できればO（n log n）以下）を考えることができるかどうか、私は思っていました。

紛らわしい場合はお詫び申し上げます。ご不明な点がございましたら、私に連絡してください。

編集：

この問題は大きな問題の一部です。より大きな問題は、それぞれがA、B、C、Dのように1000個以下の整数を持つ4つの数列を持つ場合、a + b + c + d = 0となるa、b、c、dを見つけることである。

a + b + c + d = 0は、a + b = - （c + d）を意味するので、私は問題を解決する最速の方法につながると考えました。誰かがもっと速い方法を考えることができるなら、それを私と共有してください。

ありがとうございます！ :)

Answer 1

あなたの問題は、要素の組み合わせがO（n^2）ではなく、むしろO（n^4）アルゴリズムで終わるために2つのそのようなプロセスを結合しているということです。私はあなたが今まで0以上になるまで=> 1つの方法を見つける必要があると仮定するつもりです。以下の方法は簡単に拡張してすべてウェイが必要な場合に見つけることができます。

あなたが受け入れられた値の比較的狭い範囲を持っていることを考えると、ここにあなたが何（のは、それらのMINとそれぞれMAXを呼ぶことにしましょう、+ 25Kに-25k）：

サイズの2つのint型の配列（MAX作成 - MINを+ 1）、 "indicesA"、 "indicesB"である。現代のシステムではそれほど心配することはありません。

あなたがやっていたように、リストAとBのすべての要素をループします。（あるとして-ので、私はそれが有効かどうか分からないのpythonとあまり慣れていない）、この擬似コードのようなものを実行します。

for idxA, valA in enumerate(A): 
    for idxB, valB in enumerate(B): 
     indicesA[valA + valB - MIN] = idxA + 1 
     indicesB[valA + valB - MIN] = idxB + 1 

今すぐにループするときだけでO（1）ルックアップテーブルとしてこれを使用します上のループによりルックアップテーブルを充填（ここで、N^2未満〜50K）

- O（MIN MAX）：BおよびC：0と

for valC in C: 
    for valD in D: 
     neededVal = -(valC + valD) - MIN 
     if indicesA[neededVal] > 0: 
      print('Found solution: {0} {1} {2} {3}'.format(A[indicesA[neededVal] - 1], 
       B[indicesB[neededVal] - 1], valC, valD)) 

• ルックアップテーブルの初期化B：O（n^2）
• CとDとcheのループO（n^2 +（MAX-MIN））=〜O（n^2）で与えられた値を用いて、O（n^2）

おそらくそれよりはるかに良くすることはできません。