正の整数と負の整数の両方の整数の配列が与えられた場合、合計が 0 となる特定の数値になる 4 つの異なる数値を見つけることO(n^4)は、明らかに適切な解決策ではありません。例えば
配列が含まれています
0,1,-4,3,7,-8, -11
ここで、可能な解は 0,1,-4,3 または 0,1,7,-8 または 1,3,7,-11 です。
同じ値を繰り返すことができます.それはまったく問題ではありません.選択された4つの数値は異なるインデックスを持つ必要があることに注意してください.それだけです.
効率的な解決策に関するいくつかの資料を見つけましたが、満足できるものではありませんでした.誰かが私を助けることができれば、あなたは大歓迎です.
ありがとう。
さて、http://en.wikipedia.org/wiki/3SUMから始めて、足し合わせると 0 になる 3 つの数字を見つけることについてですが、(関連する (?) ナップザックの問題と同様に) 本当に優れた方法はないと思います。 4つの数字のいずれかを行います。
ここで、0 ではなく c になる 3 つの数値を見つける問題を解決するために 3SUM アルゴリズムを適用できると想定しています。別の定数。それがうまくいかない場合は、3SUM を実行する前に、いつでもすべての整数に 3 を掛けて、それぞれから定数を引くことができます (事実上、3 つの整数を加算しているので、各整数から c/3 を減算したいのですが、アルゴリズムは整数と言っています数...）。
4 番目の数値は、別の要素 "n" を導入する可能性があります。すべての数値を反復処理し、4 番目の数値を定数に組み込みます。したがって、3SUM の場合は n^2、4SUM の場合は n^3 になります。