双方向ポインタで和 = K
双方向ポインタで和 = K
このレッスンで分かること
- ソート済みなら全探索の罠を避けられる
- ソート済みの配列
arrと整数kが与えられたとき、arr[i] + arr[j] == kとなるペアが 存在するか を判定したい- 左端に
left = 0、右端にright = n - 1を置きます
双方向ポインタで和 = K とは
ソート済み配列の両端から
leftとrightを動かして、和がKになるペアをO(n)で見つける双方向ポインタ法を学ぶ。
ソート済みの配列 arr と整数 k が与えられたとき、arr[i] + arr[j] == k となるペアが 存在するか を判定したい。素直に O(n^2) の二重ループで全ペアを試すこともできますが、配列がソート済みであるという性質を利用すれば O(n) で解けます。それが 双方向ポインタ (two pointers) と呼ばれる定石テクニックです。
ソート済みなら全探索の罠を避けられる。両端からの 2 つのインデックスを動かすだけで線形時間に落ちる。
仕組みのイメージ
左端に left = 0、右端に right = n - 1 を置きます。和 sum = arr[left] + arr[right] を k と比較し、次の 3 通りに分岐します。
sum == kのとき、ペアが見つかったのでtrueを返すsum < kのとき、和が足りないのでleftを 1 つ右にずらして大きくするsum > kのとき、和が大きすぎるのでrightを 1 つ左にずらして小さくする
left と right がぶつかるまでこれを繰り返し、見つからなければ false を返します。1 回のループで必ず left か right が動くため、計算量は O(n) です。
動きを図で追う
なぜソートが必要か
ソート済みでない配列で同じ手順をやっても、left を右にずらしたら和が増えるとは限らないため判断ができません。単調性 があるからこそ「動かす方向」を一意に決められます。ソートされていないなら、まず O(n log n) でソートしてから両端探索する、または set を使う方法 (こちらは O(n) だがメモリを使う) に切り替えます。
ソート済み + 単調性 = 双方向ポインタが効く。これは
lower_boundやslide windowの親戚にあたる重要パターン。
Python の実装
Python
def hasPairWithSum(arr, k):
left = 0
right = len(arr) - 1
while left < right:
total = arr[left] + arr[right]
if total == k:
return True
if total < k:
left += 1
else:
right -= 1
return Falsearr が空、または 1 要素の場合でも left < right の条件で安全に False を返します。
JavaScript の実装
JavaScript
function hasPairWithSum(arr, k) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const total = arr[left] + arr[right];
if (total === k) return true;
if (total < k) left += 1;
else right -= 1;
}
return false;
}よくある間違い
1 つ目は ソートされていない配列 で双方向ポインタを使ってしまうことです。例えば [3, 1, 0] で k = 4 を探すと、ペア 3+1=4 が存在するのにアルゴリズムは false を返してしまいます。
2 つ目は left <= right と書いてしまい、同じ要素を 2 度足してしまうケースです。問題によっては自分自身を使って良い場合もありますが、本問では 異なる 2 要素 という前提なので left < right が正解です。
3 つ目は 重複要素 の扱いです。ペアの組み合わせを すべて列挙 したいときには、重複をスキップする処理を追加する必要があります。
応用パターン
双方向ポインタは「ペアの和」だけでなく、次のような問題でも使えます。
- 回文判定 (両端から文字を比較して
left == rightまで進める) - 3 つの和 =
K(1 つ固定して残り 2 つを双方向ポインタで) - ソート済み配列のマージ (片方の先頭ともう一方の先頭を比較)
- 雨水を溜める問題 (左右の最大値を更新しながら進める)
どれも「両端を動かして単調性を活かす」という発想は共通しています。O(n^2) の素朴な解法を見たら、まず「ソートや単調性を使って O(n) か O(n log n) に落とせないか」を考える癖をつけてください。
やってみよう
[1, 3, 4, 5, 7]とk = 8で動きを手で追ってみる。left=0(1)、right=4(7) の時点で1 + 7 = 8のペアが最初に見つかるはずです。[]のような空配列でfalseが返るか確認する。- 計算量が
O(n)であることを、whileループ内でleftかrightが必ず 1 動くこと、合わせて最大n回しか動かないことから説明できるかを考えてみる。 - ソートされていない配列にこの関数を適用したら、何が問題になるかを考えてみる。
双方向ポインタは「ソート済み + 線形時間」の鉄板パターン。配列・文字列問題で頻出するので体に染み込ませよう。
よくある質問
Q. 双方向ポインタはいつ使う？
A. ソート済み配列で和や差が特定値になるペアを探すときに O(n) で解けます。回文判定、コンテナで最大の水を保持する問題（Container With Most Water）など、両端から評価する系の問題で活躍します。事前にソートが必要な点に注意してください。
Q. スライド窓との違いは？
A. 両者ともポインタを 2 つ使いますが、双方向ポインタは両端から内側に動かす（主にソート済み）、スライド窓は両方左から右へ動かす（連続区間集約）という違いがあります。本質的に「複数ポインタを使う」発想は同じです。
Q. ハッシュマップとどう使い分けますか？
A. ソート済みなら双方向ポインタ O(n) + 空間 O(1)、未ソートならハッシュマップ O(n) + 空間 O(n) が候補です。前処理にソートを許容できるなら双方向ポインタが空間効率で勝ち、許容できないならハッシュマップが時間効率で勝ちます。
次のレッスン
次は スライド窓の最大和 で、スライド窓の最大和 を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 双方向ポインタ の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 双方向ポインタ とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- arr は昇順ソート済みの整数配列であると仮定して良い
- 計算量は O(n) であること (双方向ポインタ法を使う)
- left と right が同じインデックスを指すケースは無効 (i != j)
入出力例
test-cases.txt
hasPairWithSum([1,2,3,4,5], 7) → true
hasPairWithSum([1,2,3,4,5], 10) → false
hasPairWithSum([1,3,4,5,7], 8) → true
hasPairWithSum([1,3,4,5,7], 2) → false
hasPairWithSum([2,4], 6) → true
hasPairWithSum([2], 2) → false
hasPairWithSum([-3,-1,2,4], 1) → true