4つのdifferens配列

Question

から要素からの和Xを検索する。これは私の問題である：

所定数xおよび4つの配列A、B、C及びD、N個のそれぞれから、いくつかの数Aが存在するかどうかを決定Bからのb、Cからのc、およびDからのdは、x = a + b + c + dである。比較、追加、スワップがあります。最悪の場合の実行時間がn^4未満のこの問題を解決する効率的なアルゴリズムを設計します。

私はどこから始めたらいいのか分からず、助けていただければ幸いです！

Answer 1

あなたは、次の手順を実行できますAとBとCとDについても同様との間のすべてのペアを加算することにより

1. アレイ対の和を作成AB = A + B、CD = C + Dを（AB及びはO（n^2）
2. ソート配列AB、CD - - N はO（n^2ログ（）CDは、n^2つの要素毎）のアレイである。）このアプローチのuser58697から（クレジット以前I複雑さが増していくと思ったのとは違うアプローチを提案しましたが、彼は私の間違いを指摘しました）。
3. ABIは=（N^2-1）CDI、= 0

4. はABは[ABI] + CD [CDI]、条件及びインクリメント/デクリメント指数をチェック調査ダイス

   1. 計算合計= AB [ABI] + CD [cdi]
   2. 合計がxの場合、SUCH COMBINATION EXISTS！ （ストップ・アルゴリズム）
   3. 場合和< X：増分CDI（++ CDI）
   4. 場合和> X：デクリメントABI（--abi）
   5. （ABI < 0）場合、または（CDI> = N^2）：そのような組み合わせは存在しない！ （アルゴリズムを停止する）
   6. 4.1に戻る。

   私たちはインデックスステップ4を行うたびにどちらかでインクリメントまたはデクリメント（またはアルゴリズムが停止した）ので、ステップ4では、最大2 *をやっているのn^2回（両方の配列全体の要素の数） - O（N^2）

したがって、すべてのすべてで、我々が持っているはO（n^2ログ（N））