ツーポインタ
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 / よくある落とし穴
ソートされていないデータに適用してしまう。
順序がないと、ポインタを動かしても候補が単調に変化しない。 まずソートする。さもなくば、これは正しい道具ではない。
while left < right の境界条件で 1 ずれる。ペアが異なる 2 つの添字を要求するときは
<;同じ添字単独で関係を満たせる稀な場合のみ <= を使う。重複をスキップし忘れる。
3Sum のような問題では、一致した後に両側で等しい隣接要素をスキップしないと、 次の反復で同じペアを 2 度出力してしまう。
06 / LeetCode で練習
簡単15
01Palindrome Number— LC 9→02Remove Duplicates from Sorted Array— LC 26→03Remove Element— LC 27→04Merge Sorted Array— LC 88→05Valid Palindrome— LC 125→06Palindrome Linked List— LC 234→07Move Zeroes— LC 283→08Reverse String— LC 344→09Reverse Vowels of a String— LC 345→10Is Subsequence— LC 392→11Valid Palindrome II— LC 680→12Sort Array By Parity— LC 905→13Sort Array By Parity II— LC 922→14Squares of a Sorted Array— LC 977→15Two Sum Less Than K— LC 1099→
中級18
01Longest Palindromic Substring— LC 5→02Container With Most Water— LC 11→033Sum— LC 15→043Sum Closest— LC 16→054Sum— LC 18→06Sort Colors— LC 75→07Remove Duplicates from Sorted Array II— LC 80→08Two Sum II - Input Array Is Sorted— LC 167→093Sum Smaller— LC 259→10Longest Word in Dictionary through Deleting— LC 524→11K-diff Pairs in an Array— LC 532→12Shortest Unsorted Continuous Subarray— LC 581→13Valid Triangle Number— LC 611→14Advantage Shuffle— LC 870→153Sum With Multiplicity— LC 923→16Max Number of K-Sum Pairs— LC 1679→17Maximum Distance Between a Pair of Values— LC 1855→18Maximum Tastiness of Candy Basket— LC 2517→
— / どれをいつ使うか
収束
配列がソート済みで、答えがペアの場合に使う。
2-sum · 回文 · コンテナ
速い / 遅い
その場での修正や循環検出に使う。
重複削除 · リストの循環
スライディングウィンドウ
条件が連続した区間に関わる場合に使う。
最長/最短 · 高々 k