2
与えられた3ソートされた配列。 a + b = cとなるように、各配列から1つずつ3つの要素を探します。それはO（n^3）時間の複雑さよりも少ないことができますか？私を助けてください。複数ソートされた配列とその複雑さの検索
A
答えて
2
aとbの2つの配列を反復し、3番目の配列のcをバイナリ検索することによって、O（N^2 * logN）の複雑さで実行できます。
もう1つの方法は、配列の要素をハッシュに挿入し、他の2つの配列のaとbを繰り返し、c =（a + b）が存在するかどうかを調べることでO（N^2）ハッシュ。
4
コール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）である。
方法2の場合、すべての3つの配列が既にソートされているので、効率的に解決する方法はありますか？ – Neel
O（N^2）よりも（a、b）のペアを生成できません...ハッシュの検索はO（1）です。 – gabitzish