通ってくる整数のストリームがあります。問題は、最初のの数字のペアがストリームから特定の値（たとえば、k）に追加されることを見つけることです。静的配列でストリーム内の特定の値に最初に追加される数字のペア
、一つは以下のいずれかを使用することができ近づく：
しかし、これらのアプローチのいずれも、ストリームのためにうまくスケーリングできません。効率的にこれを解決する上での任意の考えですか？
少なくともO（n）メモリを使用しないでこれを行う方法はないと思います。ここでnはkと合計する最初のペアの前に表示される要素の数です。私はRAMマシンを使用していると仮定していますが、ひどいbitwise hackeryを許可するマシンではありません（換言すれば、ビットパッキングでは何もできません）。
プルーフスケッチは次のとおりです。最初のペアの前に出現するn個の要素のすべてをkに合計することはしないとします。次に、kを得るために以前の値の和であるn番目の要素を見ると、それがペアになる前の要素を破棄し、kの合計に達しているかどうかわからなくなる可能性があります。より正式には、最初のn - 1要素を見て、何らかの要素xを保存していないことに気付いたとき、敵がメモリに格納していた値を見ることができると仮定します。次に、敵はストリームの次の要素をk-xに設定し、xを見たことがないので、合計に達していないと誤って報告します。
私たちが見たすべての要素を保存する必要があることを考えれば、ストリーム内の数値について詳しく知ることなく、非常に良いアプローチは、これまで見た要素のすべてを含むハッシュテーブルを使用することです遠い良好なハッシュテーブルが与えられれば、期待されるO（n）メモリとO（n）時間がかかるでしょう。
ストリームの数値の種類についてより強力な前提を設定すると、この問題を解決するためのより巧妙な戦略があるかどうかはわかりませんが、これは時間と空間の点で漸近的に理想的であると確信しています。
希望すると便利です。
あなたは有効なポイントを作成します。私は、私が概説した2つのアプローチ以外に、この問題を解決するよりスマートな方法があるかどうかを見たいと思っていました。私は、質問の「最初の数字のペア」に現金を入れることができるかどうかを確かめようとしていました。 – Bugaboo
ハッシュテーブルの何が問題ですか？ –
さて、私たちはこの膨大な数の数値をハッシュしなければならないでしょう。第2に、すべての要素について、そのペアがストリームにまだ現れていない可能性があるので、そのペアを探し続ける必要があります。しかし、私は、ハッシング手法がソート手法よりも拡張性があることに同意します。 – Bugaboo
ストリームを処理して最初のペアで停止するときにハッシュを構築できます。 –