algorithm - ソートされた配列で、合計が K になる整数のペアを見つける

Question

ソートされた整数の配列が与えられた場合、合計が K になる整数のペアを見つけるにはどうすればよいでしょうか?

例: array = 1,3,5,6,10、K = 6答えは 1 と 5 です。

時間の複雑さは最小限に抑える必要があります。

Answer 1

このブログ投稿をご覧になることをお勧めします。

http://www.codingatwork.com/2011/07/array-sum/

私のアプローチは、 のリストのバイナリ検索を実行し、K/21 つの変数aを左に、別の変数bを右に移動して、解を見つけようとすることa+b=Kです。

アイデアはa、以下の最大数からK/2開始bし、 より大きい最小数から開始することですa。繰り返しますが、バイナリ検索を使用して、配列内の次の要素を見つけaてみましょう。bそれで

• ならa+b = K、return (a,b)。
• の場合、 1 つ右の位置にa+b < K移動します。b
• の場合、 1 つ左の位置にa+b > K移動します。a

もちろん、バイナリ検索をスキップしてa、配列の先頭とb末尾から開始してから実行することもできます。

• ならa+b = K、return (a,b)。
• の場合、 1 つ右の位置にa+b < K移動します。a
• の場合、 1 つ左の位置にa+b > K移動します。b

これはおそらく高速です。