与えられたのは数字の配列です：
1, 2, 8, 6, 9, 0, 4
合計が値N（この例では11）になる3つのグループのすべての数値を見つける必要があります。ここで、3つのグループで可能な数は次のとおりです。
{1,2,8}, {1,4,6}, {0,2,9}
私が考えることができた最初の解決策はO（n ^ 3）でした。後で、次のアプローチで少し（n ^ 2 log n）を改善できます。
1. Sort the array.
2. Select any two number and perform binary search for the third element.
他のいくつかのアプローチでさらに改善できますか？
あなたは確かにそれを行うことができますO(n^2): 配列内のそれぞれiについて、他の 2 つの値の合計が になるかどうかをテストしN-iます。
O(n)ソートされた配列内の 2 つの値の合計が になるかどうかkを、両端から一度にスイープすることでテストできます。2 つの要素の合計が大きすぎる場合は、「右から左」のインデックスを減らして小さくします。合計が小さすぎる場合は、「左から右」のインデックスを増やして大きくします。機能するペアがあれば、それらを見つけることができ、2*nどちらか一方の端で道路を使い果たす前に、ほとんどの反復を実行します。として使用している値を無視するコードが必要になる場合がありますがi、ルールが何であるかによって異なります。
代わりに、ある種の動的計画法を使用して、 から作業を進めることができNますO(n*N)。現実的には、それが良いとは思いません。すべての数値が負ではないように見えるため、開始する前にそれnよりもはるかに大きい場合はN、配列から大きな値をすばやく破棄したり、3 コピーを超える重複を破棄したりできます。各値 (または3*i == Nの 3 番目のコピーを破棄する前に確認する限り、2 つのコピーi)。そのステップの後、nですO(N)。