algorithm - 複数の並べ替えられた配列での検索とその複雑さ

Question

3 つの並べ替えられた配列が与えられます。a+b=c となるように、各配列から 1 つずつ、3 つの要素を見つけます。O（n ^ 3）時間の複雑さ未満で実行できますか？私を助けてください。

Answer 1

3 つの配列をA、、 、要素を 、 、と呼びます。BCabc

最初の 2 つの配列をループしている間、aが固定されてbいるため、増加するだけであり、増加するcこともできます。

したがって、 andCのペアがあるたびにループする必要はありません。ループしながらループするだけです。abCB

ここで、3 つの配列すべての長さが O(N) であると仮定します。時間計算量は O(N^2) です。これは、 の各値について、O(N) である のすべてとすべてをA通過する必要があるためです。BC

Answer 2

O(N^2 * logN) の複雑さで実行するには、a と b の 2 つの配列を反復処理し、3 番目の配列で c をバイナリ検索します。

別の方法は、配列の 1 つの要素をハッシュに挿入し、他の 2 つの配列で a と b を繰り返し、c = (a + b) がハッシュに存在するかどうかを調べる O(N^2) です。