ツーポインタ
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 / よくある落とし穴
縮める処理は
if ではなく while で。1 回の縮小だけでは不変条件が戻らないことが多い。窓が妥当になるまで内側ループを回す — そうでないと壊れた窓を次のステップへ持ち越してしまう。
答えを記録するタイミングが間違っている。
best の更新は、縮小の後、窓が妥当な状態で行う。 縮小中の中間状態は答えではない。窓長の境界条件で 1 ずれる。
閉区間なら長さは
right − left + 1、半開区間なら right − left。どちらかに統一し、決して混ぜないこと。06 / LeetCode で練習
簡単3
中級29
01Longest Substring Without Repeating Characters— LC 3→02Longest Substring with At Most Two Distinct Characters— LC 159→03Minimum Size Subarray Sum— LC 209→04Longest Substring with At Most K Distinct Characters— LC 340→05Longest Substring with At Least K Repeating Characters— LC 395→06Longest Repeating Character Replacement— LC 424→07Find All Anagrams in a String— LC 438→08Max Consecutive Ones II— LC 487→09Subarray Sum Equals K— LC 560→10Permutation in String— LC 567→11Fruit Into Baskets— LC 904→12Binary Subarrays With Sum— LC 930→13Subarray Sums Divisible by K— LC 974→14Max Consecutive Ones III— LC 1004→15Grumpy Bookstore Owner— LC 1052→16Get Equal Substrings Within Budget— LC 1208→17Replace the Substring for Balanced String— LC 1234→18Count Number of Nice Subarrays— LC 1248→19Maximum Number of Occurrences of a Substring— LC 1297→20Number of Substrings Containing All Three Characters— LC 1358→21Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit— LC 1438→22Maximum Number of Vowels in a Substring of Given Length— LC 1456→23Longest Subarray of 1's After Deleting One Element— LC 1493→24Check If Array Pairs Are Divisible by k— LC 1497→25Maximize the Confusion of an Exam— LC 2024→26K Radius Subarray Averages— LC 2090→27Maximum Sum of Distinct Subarrays With Length K— LC 2461→28Take K of Each Character From Left and Right— LC 2516→29Maximum Sum of Almost Unique Subarray— LC 2841→
難しい11
01Substring with Concatenation of All Words— LC 30→02Minimum Window Substring— LC 76→03Contains Duplicate III— LC 220→04Sliding Window Maximum— LC 239→05Sliding Window Median— LC 480→06Minimum Window Subsequence— LC 727→07Shortest Subarray with Sum at Least K— LC 862→08Subarrays with K Different Integers— LC 992→09Minimum Number of Operations to Make Array Continuous— LC 2009→10Maximum Number of Robots Within Budget— LC 2398→11Count Subarrays With Fixed Bounds— LC 2444→
— / どれをいつ使うか
収束
配列がソート済みで、答えがペアの場合に使う。
2-sum · 回文 · コンテナ
速い / 遅い
その場での修正や循環検出に使う。
重複削除 · リストの循環
スライディングウィンドウ
条件が連続した区間に関わる場合に使う。
最長/最短 · 高々 k