[最近、同様の質問をしました。並べ替えられていない配列で、合計が1の値になり、すばらしい回答が得られた3つの要素を検索してください。ありがとうございます。:)]
次の問題を解決するためにあなたの助けが必要
です：私はアルゴリズムを探しています、時間計算量はϴ（n³）でなければなりません。
アルゴリズムは、（n個の整数の）ソートされていない配列を検索して、合計が指定されたzになる5つの異なる整数
を探します。
例：入力用： ({2,5,7,6,3,4,9,8,21,10} , 22)
出力は、true2 + 7 + 6 + 3 + 4 = 22を合計できるためのものでなければなりません
（並べ替えは実際には重要ではありません。複雑さに影響を与えることなく、配列を最初に並べ替えることができます。
したがって、配列がすでにソートされているかのように問題を見ることができます。）
-メモリの制約なし-
-配列要素がn個の整数であることがわかっているだけです。-
どんな助けでも適用されるでしょう。
アルゴリズム：
1）初期整数のペアで構成される配列を生成し、並べ替えます。そのステップにはO（n ^ 2 * log（n ^ 2））時間がかかります。
2）初期配列から値を選択します。O（n）の方法。
3）これで、リンクされた問題と非常によく似た問題が発生します。それらの合計がz-選択された値に等しくなるように2つのペアを選択する必要があります。ありがたいことに、長さO（n ^ 2）の、すでにソートされているすべてのペアの配列があります。このようなペアを見つけるのは簡単です。3整数和問題で行ったのと同じことです。2つのポインターを作成し、両方を合計O（n ^ 2）回移動します。
O（n ^ 3）全体の複雑さ。
選択した値で構成されるペアを見つける際に、いくつかの問題が発生する可能性があります。選択した値で構成されるすべてのペアをスキップします（存在しなかったようなペアに到達したら、ポインターをさらに移動します）。
sum（p1）+ sum（p2）+選択された値= zのように、p1とp2の2つのペアがあるとします。p1とp2のすべての整数が異なる場合は、解決策があります。そうでない場合は、それが少し厄介になるところです。
p1を修正し、p2の次の値を確認してみましょう。2つの異なるペアが同じ合計を持つことができるため、p2と同じ合計になる可能性があります。もしそうなら、間違いなく、p2と同じようにp1と衝突することはありませんが、p1の他の整数と衝突する可能性があります。もしそうなら、p2の後の2番目の値もチェックしてください。同じ合計がある場合は、p1との衝突は絶対にありません。
したがって、p1またはp2と同じ合計を持つペアが少なくとも3つあると仮定すると、固定p1の3つの値をチェックするか、固定p2の3つの値をチェックするソリューションが常に見つかります。
残っている唯一の可能性は、p1と同じ合計のペアが3つ未満であり、p2と同じ合計のペアが3つ未満であるということです。最大4つの方法でそれらを選択できます-それぞれの可能性を確認するだけです。
少し不快ですが、一定量の操作でそのような問題を処理することができます。つまり、全体の複雑さはO（n ^ 3）です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加