ツーポインタ
01 / 共通の仕組み
同じ列上を 2 つの添字が動いて、ある 不変条件を保つ — 移動規則はサブパターンごとに違っても、仕組みは共通している。
02 / 一文での本質
同じ列を異なる速度で進む 2 つのポインタ — その速度差によって、追加メモリなしにその場で圧縮したり、 中点を見つけたり、サイクルを検出できる。
問題ソート済み配列からその場で重複を除く入力[1, 1, 2, 2, 3, 3]
10
11
22
23
34
35
ソート済み入力。先頭の要素は常に残す — slow は 0、fast は 1 から走査を始める。
ステップ
0 / 8
slow · fast
0 · —
動作
初期化
ここまでの一意数
1
0 / 8
03 / パターンの骨格
# その場圧縮の変種slow ← 0for fast in 1..n−1:if arr[fast] ≠ arr[slow]:slow++arr[slow] ← arr[fast]return slow + 1# サイクル検出の変種: fast は 2 倍速、slow は 1 倍速 — サイクルがあるとき、かつそのときのみ出会う
04 / このパターンを使うべき合図
「その場」
別の配列を確保せず、入力を直接書き換える必要がある。 slow は次に残す要素を置くべき位置を指す。
「サイクル」
連結リストやポインタ列でサイクルを検出・特定する。 fast は slow の 2 倍速で進み、サイクルがあるとき、かつそのときのみ出会う。
「中点」
1 回の走査でリストの中点を求める: fast が末尾に到達したとき、slow はちょうど中央にいる。
「圧縮 / 分割」
ある述語を満たす要素を前方に集め、それ以外を捨てる。重複除去と同じ仕組みで、保持条件だけが異なる。
05 / よくある落とし穴
i.
両ポインタを同じ位置から始めてしまう。
圧縮では
slow は 0、fast は 1 から始める。サイクル検出ではどちらも先頭から始めるが、 最初の比較の前に fast を進める。問題ごとに約束を選ぶ。ii.
slow を進めるタイミングを誤る。
書き込みの前に
slow を進める。後にしてはいけない — そうしないと直前に残した値を上書きしてしまう。 この 1 ずれが、正しい結果と全体がずれた結果の境目になる。iii.
スライディングウィンドウと混同する。
スライディングウィンドウは連続区間の大きさを測る道具。Fast/Slow は非対称な速度を使い — 2 つのポインタ間の間隔そのものが答え(あるいは信号)であって、データ上の窓ではない。
06 / LeetCode で練習
難易度順に 4 問。前半 2 問は配列の圧縮、後半 2 問は連結リストの古典問題。
— / どれをいつ使うか
収束
配列がソート済みで、答えがペアの場合に使う。
2-sum · 回文 · コンテナ
速い / 遅い
その場での修正や循環検出に使う。
重複削除 · リストの循環
スライディングウィンドウ
条件が連続した区間に関わる場合に使う。
最長/最短 · 高々 k