尺取り法(2ポインタ)とは？
尺取り法(Two Pointers)は、整列配列で2つのインデックスを両端(または同じ方向)から動かし、O(n)で答えを見つける技法です。全ペアを調べる二重ループのO(n²)を、一度のスキャンO(n)に減らすのが核心です。
代表例: 整列配列で和がtargetになる2数を見つける。 左ポインタは0、右ポインタは末尾から始めます。
なぜO(n)で動くのか
配列が整列されている点が鍵です。
- •指している和がtargetより大きい → 最大候補(右)を減らすので
right-- - •和がtargetより小さい → より大きい値が必要なので
left++ - •和が等しい → 正解
この単調性(片方を減らすと和が減り、増やすと和が増える)のおかげで、一度捨てた候補を再び見る必要がありません。各ポインタが一方向にのみ動くので全体がO(n)です。
動作原理
ステップ1. left = 0、right = n - 1 とします。
ステップ2. sum = arr[left] + arr[right] を計算します。
ステップ3. sum == target なら正解、sum > target なら right--、sum < target なら left++。
ステップ4. left < right の間ステップ2〜3を繰り返します。
AlgoNoteの可視化は、和に応じて左右のポインタが内側へ狭まる過程をステップごとに示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(n)(未整列ならO(n log n)を先行) |
| 空間 | O(1) |
例で追ってみる
arr = [1, 2, 4, 7, 11]、target = 9。
- •left=0(1), right=4(11): 和12 > 9 → right--
- •left=0(1), right=3(7): 和8 < 9 → left++
- •left=1(2), right=3(7): 和9 = 9 → 正解
(2, 7)
変形
- •同方向の2ポインタ: 両方が片側から出発し窓を広げ縮めるスライディングウィンドウ。
- •3数の和: 1つを固定し残り2つに尺取り法。
- •重複除去・統合: 整列済み2配列を同時に走査。
よくあるミス
- •整列前提の無視: 未整列配列にそのまま使うと単調性が崩れ誤答です。
- •境界条件:
left < right(または<=)を問題に合わせて選び、同じ要素を2回使わないようにします。 - •重複ペアの処理: 全ペアを探す問題なら、ヒット後に両ポインタを適切に進め重複を飛ばします。
AlgoNoteで直接確認しましょう
和とtargetの大小に応じて左右のポインタがどう動くかをAlgoNoteでステップごとに確認できます。