私は2つかかるアルゴリズムを作ろうとしています配列、n個の整数と整数kのSとT。アルゴリズムは、配列に整数sとtがあるため、s + t = kが存在するかどうかをチェックします（Sがs、Tがt）。
配列をソートする何かを考えてみましたTとforループを使用してSを経由し、バイナリ検索を使用して、Sのすべての要素に対してk-S [i]のような整数が見つかるかどうかを確認します。
コードを書く人を探していません。いくつかのアイデアを得るためにここにだけ尋ねます。
回答：
回答№1は62つのリストを並べ替えます。これはO（n log n）です。
次に、2つのイテレーターをセットアップします。 1つの反復子は 最低 Sの値は増加し、Sの値は増え続けます。他の反復子は 最高 Tの値であり、減少する値を反復処理します。
次を繰り返します。
- 現在の値が合計値よりも大きい場合 k、Tイテレータを進めます。これにより、合計が減少します。
- 現在の値が合計値よりも小さい場合 k、Sイテレーターを進めます。これにより合計が増加します。
- 現在の値の合計が k、成功して終了します。
この2番目のフェーズは、せいぜい2Nの前進を引き起こすはずであり、したがってO（n）です。したがって、合計の複雑さはO（n log n）です。
これは、繰り返されるバイナリ検索と同じ複雑さを持ちますが、このアルゴリズムは、特に大規模な場合、より高速になるはずです。 n.
回答№2の場合は3
実際に指定したアルゴリズムには、両方の配列の要素の総数がO（n）であると仮定して、ランタイムO（n log n）があります。これは次のとおりです。
- 配列の1つをソートします（O（n log n））
- 他の配列の各要素について：（O（n）iterations）
- 相補的な要素が他の配列にあるかどうかを確認するためにバイナリ検索を実行します（O（log n）time）
最初のステップには時間O（n log n）がかかり、2番目のステップはO（log n）アルゴリズムのO（n）回の反復で構成され、したがってO（n log n）の時間もかかります。 O（n log n）+ O（n log n）= O（n log n）なので、アルゴリズムは時間O（n log n）で実行されます。あなたが探している「アルゴリズムを正確に手に入れた」ようです！
お役に立てれば！
回答№3の場合は3
ソート どちらも 配列。それらをステップインする 反対の 行き方。 2つの要素の合計がkより小さい場合、「増加する」ポインタを進め、kより大きい場合、減少するポインタをステップします。この方法は、配列の1つのみをソートするよりも少し遅いかもしれませんが、最終パスは間違いなく高速です。おそらく、2つの配列の先頭部分と末尾部分をスキップ（削除）できるため、おそらく短くなります。
答え№4の2
あなたのアプローチは正しいようです。最初に配列をソートし、2つのO（n log n）操作を実行してから、n個のバイナリ検索（それぞれO（log n））を実行します。
回答№5の2
ソートはO（n log n）です。次に、O（n）個の最初の要素ごとに、一致する要素をO（log n）検索します。それは合計でO（n log n）のように聞こえます（関数fに対してO（f）+ O（f）= O（f）であるため）。
答え№6の場合は0
さらに別の方法：配列の1つをハッシュテーブル（O（N））に保存します。他を通過する線形パス（O（N））を実行し、すべての要素に対してルックアップを実行します k-elem ハッシュテーブルに。合計ランタイム：2 * O（N）：= O（N）。利益！