ツーポインタ
01 / 共通の仕組み
同じ列上を 2 つの添字が動いて、ある 不変条件を保つ — 移動規則はサブパターンごとに違っても、仕組みは共通している。
02 / 一文での本質
入力がソート済みで、答えがある関係を満たすペアのとき、 ポインタを両端に置き、比較結果に応じて誤った側を動かす — 各移動は比較によって一意に決まる。
問題arr[i] + arr[j] = target を満たす i, j を求める入力[1, 2, 4, 7, 11, 15]目標値9
10
21
42
73
114
155
ソート済み入力、target 9。left を先頭、right を末尾に置く。
ステップ
0 / 8
L · R
—
arr[L] + arr[R]
—
目標との比較
—
0 / 8
03 / パターンの骨格
# ソート済み列を走る 2 つの添字left ← 0right ← n − 1while left < right:// 比較してどちら側を動かすか決めるif arr[left] + arr[right] = target:return (left, right)elif sum < target:left++ // より大きな和が必要else:right-- // より小さな和が必要
04 / このパターンを使うべき合図
「ソート済み」
入力が既にソートされているか、低コストでソートできる。 順序性こそが各移動を確定的にする。
「ペア」
答えはちょうど 2 つの要素に関わる — 和、差、あるいは一致。
「回文 / 鏡像」
両端から内側へ文字を比較するような、検証可能な対称構造を持つデータ。
「最も近い」
完全一致ではなく距離を最小化する問題 — 収束する間、最良のペアを記録し続ける。
05 / よくある落とし穴
i.
ソートされていないデータに適用してしまう。
順序がないと、ポインタを動かしても候補が単調に変化しない。 まずソートする。さもなくば、これは正しい道具ではない。
ii.
while left < right の境界条件で 1 ずれる。ペアが異なる 2 つの添字を要求するときは
<;同じ添字単独で関係を満たせる稀な場合のみ <= を使う。iii.
重複をスキップし忘れる。
3Sum のような問題では、一致した後に両側で等しい隣接要素をスキップしないと、 次の反復で同じペアを 2 度出力してしまう。
06 / LeetCode で練習
難易度順に 4 問。前半 3 問はソート済みの入力を要求し、4 問目はソート可能な入力でこのパターンを試す。
— / どれをいつ使うか
収束
配列がソート済みで、答えがペアの場合に使う。
2-sum · 回文 · コンテナ
速い / 遅い
その場での修正や循環検出に使う。
重複削除 · リストの循環
スライディングウィンドウ
条件が連続した区間に関わる場合に使う。
最長/最短 · 高々 k