2つのポインタを一方向に動かすことで、二重探索を線形走査に置き換えられる場合があります。除外した位置を再び調べる必要がないことの証明が重要です。
2つのポインタで候補を除外する過程を示すシミュレーター
モードと目標値を変更して試してください。薄いセルは候補から除外済みです。
時間計算量O(n)
追加領域O(1)
両端から近づく整列が必要
同じ方向に進む正の値が前提
両端から近づく
2要素の和が小さければlを進め、大きければrを戻します。残りの最大値と組んでも足りないa[l]は安全に除外できます。この議論には整列済みの配列が必要です。
同じ方向に動かす
rで広げ、和の条件を満たしたらlで縮めます。正の値なら拡張で和が増え、縮小で減ります。負数があると単調性が崩れます。和が指定値になる区間の個数には 累積和とハッシュを組み合わせる方法があり、しきい値以上の最短区間には別の技法が必要なことがあります。
よくある演習
典型例には整列済み配列の2要素の和、1つを固定するO(n²)の3要素の和、整列済み配列のマージ、正数列の最短区間、下限を満たす最小の差などがあります。