双方向ポインタで和 = K

総当たりは、1 万個で 5,000 万回

昇順に並んだ配列から、足して k になる 2 つを探します。素直にやるなら、すべての組を試すことになります。

5 個で 10 回なら気になりませんが、組の数は要素数の 2 乗に比例して増えます。1 万個なら約 5,000 万回。ここで効いてくるのが「すでに並んでいる」という前提です。

端から詰めると、1 回の比較で片側がまとめて消える

左端と右端に印を置き、その 2 つの和を見ます。[200, 350, 480, 620, 900] から合計 830 の組を探してみます。

• 200 + 900 = 1100。大きすぎる。右の印を 1 つ内側へ
• 200 + 620 = 820。足りない。左の印を 1 つ内側へ
• 350 + 620 = 970。大きすぎる。右の印を内側へ
• 350 + 480 = 830。見つかった

4 回で終わりました。大事なのは、印を動かすたびにまだ試していない組がまとめて捨てられていることです。1 回目で 200 + 900 が大きすぎたとき、200 と組める相手のうち 900 が最大なのですから、200 との組はもう望みがありません。それどころか 900 は、200 よりも大きい値としか組めなくなるので、900 を含む組が丸ごと消えます。

足りないときは逆です。左端の値は、いまの右端より小さい相手としか組めないので、これ以上小さい相手を試す意味がありません。だから左を内側へ動かします。

どちらの印も外側へは戻らないため、2 つ合わせても要素数ぶんしか動きません。見つからなかった場合でも、比較の回数は要素数より少なく済みます。総当たりが 5,000 万回だった 1 万個の配列なら、多くても 1 万回です。

並んでいない配列に使うと、あるのに「ない」と答える

この方法が成り立つのは、「足りないなら左を大きくするしかない」と言い切れるからです。並んでいない [3, 1, 0] で 4 を探すと、3 + 0 = 3 で足りないので左を動かし、1 + 0 = 1 でまた足りず、印がぶつかって「無い」と答えます。3 + 1 が答えなのに見逃しました。

例外も出さずに静かに間違えるので、いちばん怖い使い方です。使う前に、入力が並んでいるかどうかを必ず確かめてください。

よくある間違い

印がぶつかったところで止めず、同じ位置まで許してしまうことです。左右が同じ要素を指したとき、その値を 2 回足した和を見ています。同じものを 2 つ選んでよい問題なら正しいのですが、異なる 2 つを探すなら、印が重なる前に打ち切ります。

1. arr は昇順ソート済みの整数配列であると仮定して良い
2. 計算量は O(n) であること (双方向ポインタ法を使う)
3. left と right が同じインデックスを指すケースは無効 (i != j)