複数ソートされた配列とその複雑さの検索

Question

与えられた3ソートされた配列。 a + b = cとなるように、各配列から1つずつ3つの要素を探します。それはO（n^3）時間の複雑さよりも少ないことができますか？私を助けてください。

Answer 1

aとbの2つの配列を反復し、3番目の配列のcをバイナリ検索することによって、O（N^2 * logN）の複雑さで実行できます。

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

Answer 2

コール3つの配列A、BとC、および要素a、bとc。

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

だから、Cをループするためにあなたがaとbのペアを持っているすべての時間を持っていません。ちょうどをループしながらループしますが、Bとなります。

今その数、すべての3つの配列は、長さO（N）を持つA内の各値のために、あなたはBとCのすべてのすべてを通過する必要があるため、時間の複雑さは、O（N^2）であると仮定O（N）である。