【にポインタほう】
二ポインタ法 とは？
最終更新:
💡 2つの位置を動かし、候補を正しく絞る
配列などの2つの位置を管理し、条件に応じて進める探索の技法。位置を戻さず各更新が定数時間なら走査をO(n)にできますが、ソートの前処理や外側の繰り返しを含む全体の計算量は別に評価します。
📌 このページのポイント
- ポインタは位置を表し、Cのメモリアドレスだけを意味しない
- 両端から近づける、同方向に進めるなどのパターンがある
- 2つの位置を持つだけで、すべての問題がO(n)になるわけではない
- ソート済み2SUMでは、和の大小を使って不要な候補を除ける
- 正しく候補を捨てられる条件と、前処理を含む計算量を説明する
ひよこ 二ポインタ法は何をする？
ペンギン先生 ひよこ 候補を飛ばしても大丈夫？
ペンギン先生 昇順という条件が理由になるよ。左の値と右の値の和が10より大きければ、その右の値を残して左だけ増やしても和は小さくならない。だから右を小さい側へ動かせる。和が小さい場合は逆に左を増やす。条件に基づいて不要な候補を除くんだ。
ひよこ いつでもO(n)になる？
ペンギン先生 ひよこ 同じ方向に動かす方法もある？
ペンギン先生 あるよ。読み取り位置と書き込み位置で重複を除いたり、区間の左右の端を動かしたりする方法だね。ただし合計に基づいて区間を縮める場合、負の値があると和が単調に変わらず、正の値だけのときと同じ規則をそのまま使えないことがあるんだ。
ひよこ 実装で何を確認する？
もっと詳しく知りたい人へ
区間の和を計算し直してもO(n)？
各移動のたびに区間全体を足し直せば、1回の更新が定数時間ではなくなります。適用条件が合う場合は、右端の値を加え、左端の値を引くなどの更新で和を保つことが重要です。位置の移動回数と、1回の更新費用を両方評価してください。
まとめ：ざっくりこれだけ覚えればOK！
「二ポインタ法」って出てきたら「2つの位置で探索を進める技法」と思えばだいたいOK！
📖 おまけ：英語の意味
「Two Pointers Method」 ＝ 2つの位置・ポインタを使う方法
💬 配列の添字や反復子など、今見ている場所を2つ管理します。両端からの探索だけでなく、同じ方向へ進む方法も含めて説明されます。