ツーポインタ

01 / 共通の仕組み

同じ列上を 2 つの添字が動いて、ある 不変条件を保つ — 移動規則はサブパターンごとに違っても、仕組みは共通している。

02 / 一文での本質
条件を満たす連続な区間が必要なとき、 右側から広げて破綻するまで進め、 左側から縮めて再び成立するまで戻す。
問題和が ≤ k となる最長部分配列入力[3, 1, 2, 1, 4, 2, 1, 5]k8
30
11
22
13
44
25
16
57
準備完了。play を押して右側から窓を広げる。
ステップ
0 / 27
窓の和
0
現在の長さ
0
ここまでの最良
0
0 / 27

03 / パターンの骨格

# 1 つの列を走る 2 つの添字left, right ← 0while right < n:// 1. 窓を広げるarr[right] を状態に取り込むwhile 不変条件が破られている:arr[left] を除く; left++// 2. 現在の妥当な窓を記録best ← max(best, right − left + 1)right++

04 / このパターンを使うべき合図

「連続」
答えは配列の切れ目のないスライスであり、部分集合ではない。 並べ替えが許されるなら、これは正しい道具ではない。
「最長 / 最短」
制約のもとで、その連続スライスの長さを最適化する問題。
「高々 k」
単調な制約: [l,r] で成立するなら、その内側の小さな窓でも成立する。 これが窓を支える不変条件。
「k 種類」
内部状態が多重集合になるバリエーション。仕組みは完全に同じ。

05 / よくある落とし穴

i.
縮める処理は if ではなく while で。
1 回の縮小だけでは不変条件が戻らないことが多い。窓が妥当になるまで内側ループを回す — そうでないと壊れた窓を次のステップへ持ち越してしまう。
ii.
答えを記録するタイミングが間違っている。
best の更新は、縮小の後、窓が妥当な状態で行う。 縮小中の中間状態は答えではない。
iii.
窓長の境界条件で 1 ずれる。
閉区間なら長さは right − left + 1、半開区間なら right − left。どちらかに統一し、決して混ぜないこと。

06 / LeetCode で練習

難易度順に 4 問。あえて解答は載せていません。

01Maximum Average Subarray I— LC 643簡単→02Longest Substring Without Repeating Characters— LC 3中級→03Longest Substring with At Most K Distinct Characters— LC 340中級→04Minimum Window Substring— LC 76難しい→

— / どれをいつ使うか

収束
配列がソート済みで、答えがペアの場合に使う。
2-sum · 回文 · コンテナ
速い / 遅い
その場での修正や循環検出に使う。
重複削除 · リストの循環
スライディングウィンドウ
条件が連続した区間に関わる場合に使う。
最長/最短 · 高々 k