整数配列内の数字のペアを見つけるアルゴリズムwhoes sumが等しい場合

Question

整数配列whoes sumの数値のペアを見つけるアルゴリズム。 ex {1 2 3 4 6}

ここでは、合計が3 + 2 = 5,4 + 1 = 5であるため、{3 2} {4 1}が出力である必要があります。

ここで重要な点は、複雑さがO（n）であることです。このための解決策が見つかったら私を助けてください？

Answer 1

問題はO（n）で解決できますか？

入力シーケンスが{0、0、0、0、0、...、0}の場合を想像してみてください。ここでは2つのペアごとに条件を満たす。すべてのペアをリストするだけで既に少なくともO（n^2）です。

Answer 2

これが効果的にできるかどうかはわかりません。

与えられた情報によると、配列はソートされておらず、配列を2回通過する必要があると予想される合計を知ることはできません。

検索アルゴリズムを考えてみましょう。最も複雑ではないものの、線形（逐次）探索はO（n）の複雑さを有する。配列を走査するだけです。あなたが期待している合計を知っていれば、そのケースは似ており、実際にあなたがする必要があるのは線形検索です。他のものについては、より複雑になります。

しかし、あなたはあなたが合計を知っていないので、複数回にわたってトラバースする必要があります。私の頭は、これがO（n log n）かO（n^2）だと言います。

おそらく、より多くのデータ構造、おそらく総和表（2D配列???）を使用するソリューションが存在する可能性がありますが、そのようなソリューションが存在する可能性は低いです。

Answer 3

私はそれが可能だと思う：

あなたは合計の長さ= {}二番目の配列のTMPが必要です。

sum = 5 
array = {1,2,3,4,6} 
for every i in array{ 
    if i>=sum: 
     continue 
    if tmp[i] != 0 { 
     output {i,(sum-i)} 
     tmp[i] = 0 
     continue 
    } 

    tmp[sum-i] := i 
} 

それです。それほど単純ではO（n）

短所を有する： したがってあなたは6行目で確認するために、実 整数、オブジェクトを使用する必要があり、それは、{5,0}のようなペアを見つけることができません

1. 、 をNULLに変換してNULLにNULLを代入すると、 8,
2. の対が負の数値 になりません。

Answer 4

問題は、前述のように、役立ついくつかの制約がないようです。私が最初に提案したいのは、配列の各整数は異なるはずです。少なくとも、出力は固有のペアでなければなりません。

特定の問題のドメインに適用される場合と適用されない場合の別の制約は、ソートされた配列です。この制約は、真の場合、単純なアルゴリズムを示唆します。左右の2つのポインタをそれぞれの端から開始します。合計が一致する場合は出力し、左に増分し、右に減分します。一致しない場合は、合計が大きすぎる場合は右ポインタを減分するか、左（小さすぎる場合）を増分します。中央のどこかで交差するまで左右に調整を続けます。

ソートされていない配列の場合。ハッシュテーブルを作成し、すべての整数を挿入します。配列をもう一度見て、今回は必要な合計を満たす値のハッシュテーブルを検索します。ハッシュ関数が完璧な場合（達成するのが難しいもの）、予想される実行時間はO（n）です。