スライディングウィンドウ / Two pointers

配列を扱うときに、スライディングウィンドウは2つのポインタを使って効率的に問題を解くための一般的なテクニックです。基本的な考え方は、左ポインタと右ポインタを用意し、状況に応じて適切な方向にスライドさせることにあります。

たとえば、ある配列の中で理想的な範囲（部分配列）を見つけたいとします。まずは右ポインタをできるだけ進め、次に左ポインタを右に近づけて調整します。その後、再び右ポインタを進められるだけ進め、また左ポインタを調整するという手順を繰り返します。こうして最適な範囲を見つける方法が、スライディングウィンドウと呼ばれるものです。

Challenge - Find two numbers that sum up to k

ソート済みの n 個の数値が入った配列と、ターゲット値 k が与えられたとき、配列の中から合計が k になる2つの数を探してください。配列の値は昇順に並んでおり、辞書型やマップなどは使用できません。

入力

最初の行には、配列の要素数 n (1 ≤ n ≤ ) と数値 k () の2つの整数が与えられます。次の行には、空白で区切られた n 個の整数が昇順で並んでおり ()、これらが配列を構成します。

出力

配列の中から合計が k になる2つの整数を表示してください。出力する最初の整数はできるだけ小さい方の値にしてください。もし該当する2つの数が見つからなかった場合は、Impossible と出力してください。

例

チュートリアル

この配列は昇順にソートされているため、2つのポインタを配列の先頭と末尾に置いて、その合計を見ながら移動させる方法が有効です。

2つの要素の合計が k より大きい場合は右ポインタを左にずらし、小さい場合は左ポインタを右にずらします。そして、合計がちょうど k になったら、その要素を出力してプログラムを終了します。

n, k = ...                  # n と k を初期化
a = ...                     # 昇順の配列を初期化

l, r = 0, len(a) - 1        # 左と右のポインタを初期化
while l < r:                # l と r が異なる間ループ
    if a[l] + a[r] > k:     # 合計が k より大きい場合 => r を動かして合計を小さく
        r -= 1
    elif a[l] + a[r] < k:   # 合計が k より小さい場合 => l を動かして合計を大きく
        l += 1
    else:                   # a[l] + a[r] == k の場合 => 要素を出力して終了
        print(a[l], a[r])
        break
else:                       # while...else は break しなかったときに実行される
    print('Impossible')

“Two-pointers” は、さまざまな状況で応用できる汎用的な手法です。ポイントは、問題に応じて左ポインタと右ポインタの初期位置を決め、その後どのように位置を更新していくかというルールを工夫するところにあります。

今回の例では、左ポインタを配列の先頭、右ポインタを配列の末尾に置きましたが、案件によっては右ポインタも先頭に置く場面があるかもしれません。また別の scenario では、左ポインタを配列の末尾に置いて、2つのポインタを先頭に向けてスライドさせるという場合も考えられます。