配列を走査する型 — 二重ループを一重にする
配列を二重ループで舐めるコードは、件数が 1 万を超えたあたりから目に見えて遅くなります。1 億回の反復が走るからです。
このとき、**書き換えの型はそう多くありません。**問題の性質に応じて 4 つのどれかが当たります。型を知っていれば、遅いコードを見た瞬間に「これは一重にできる」と判断できます。
この章で学ぶこと
- two pointer — ソート済みの配列を両端から寄せる
- スライディングウィンドウ — 連続した範囲をずらしながら再利用する
- 累積和 — 区間の合計を前計算で
O(1)にする - 単調スタック — 「次に大きい要素」を 1 回の走査で求める
- 遅いコードを見たとき、どの型が当たるかの判定手順
共通する発想
4 つの型に共通しているのは 1 つです。内側のループが毎回ゼロからやり直している無駄を、前の結果の再利用に置き換える。
計算量の章で扱った「ハッシュで O(n²) を O(n) に落とす」も同じ系統です。あちらは「一度見た値を集合に覚える」でした。この章の 4 つは、配列の順序や連続性を使う点が違います。
two pointer — 両端から寄せる
ソート済みの配列から、和が目標値になる 2 要素を探します。素直に書くと二重ループで O(n²) です。
両端に印を置き、和が小さければ左を右へ、大きければ右を左へ動かします。
function twoSumSorted(xs: number[], target: number): [number, number] | null {
let lo = 0;
let hi = xs.length - 1;
while (lo < hi) {
const sum = xs[lo] + xs[hi];
if (sum === target) return [xs[lo], xs[hi]];
if (sum < target) lo++; // 和を大きくしたい
else hi--; // 和を小さくしたい
}
return null;
}
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10)); // [ 4, 6 ]
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 100)); // null
lo と hi は近づく一方なので、走査は合計 n 回で終わります。O(n) です。
**正しさの根拠は「捨てた組を二度と見なくてよい」ことです。**和が目標より小さいとき、lo を含む組で目標に届く可能性があるのは、より大きい相手と組んだときだけです。しかし hi は現時点で最大なので、lo はどの相手とも届きません。だから lo ごと捨てられます。
**適用条件はソート済みであること。**ソートされていない配列に使うと答えを取りこぼします。未ソートなら、まずハッシュを使う方法を検討してください。ソートに O(n log n) かかるので、再帰と分割統治の章で見たとおり全体がそこに律速されます。
スライディングウィンドウ — 連続した範囲をずらす
固定長
「連続する 3 件の合計が最大になるのはどこか」を求めます。範囲ごとに合計を計算し直すと O(n × k) です。
1 つずらすと、出ていく 1 件と入ってくる 1 件しか変わりません。
function maxWindowSum(xs: number[], k: number): number {
let sum = 0;
for (let i = 0; i < k; i++) sum += xs[i];
let best = sum;
for (let i = k; i < xs.length; i++) {
sum += xs[i] - xs[i - k]; // 入る 1 件を足し、出る 1 件を引く
if (sum > best) best = sum;
}
return best;
}
console.log(maxWindowSum([2, 1, 5, 1, 3, 2], 3)); // 9
差分だけを更新するので O(n) になります。
可変長
窓の幅が決まっていない場合は、右端を進めながら条件を満たしている間だけ左端を縮めます。
function minWindowLen(xs: number[], target: number): number {
let lo = 0;
let sum = 0;
let best = Infinity;
for (let hi = 0; hi < xs.length; hi++) {
sum += xs[hi];
while (sum >= target) { // 条件を満たす間、左を縮めて最短を狙う
best = Math.min(best, hi - lo + 1);
sum -= xs[lo++];
}
}
return best === Infinity ? 0 : best;
}
console.log(minWindowLen([2, 3, 1, 2, 4, 3], 7)); // 2
内側に while があるので二重ループに見えますが、lo は減らないので全体でも n 回しか進みません。合わせて O(n) です。
**適用条件は、範囲を広げたときと狭めたときで条件が単調に変わることです。**上の例では要素がすべて正なので、範囲を広げれば和は必ず増えます。負の数が混ざるとこの単調性が崩れ、左端を縮めてよいかの判断ができなくなります。
累積和 — 区間の合計を前計算する
区間の合計を何度も聞かれるなら、先に「先頭からの合計」を作っておきます。
function buildPrefix(xs: number[]): number[] {
const p = new Array<number>(xs.length + 1).fill(0);
for (let i = 0; i < xs.length; i++) p[i + 1] = p[i] + xs[i];
return p;
}
const xs = [4, 2, 7, 1, 9, 3];
const prefix = buildPrefix(xs);
const rangeSum = (l: number, r: number): number => prefix[r + 1] - prefix[l];
console.log(`[1,3] の和 = ${rangeSum(1, 3)}`); // [1,3] の和 = 10
console.log(`[0,5] の和 = ${rangeSum(0, 5)}`); // [0,5] の和 = 26
前計算に O(n)、以降は 1 回の質問が O(1) です。質問が q 回なら O(n + q) で、毎回数え直す O(n × q) と比べて質問が多いほど差が開きます。
先頭に 0 を置くのが実装の要点です。p[0] = 0 があるので l が 0 のときも場合分けが要りません。境界の場合分けはバグの温床なので、この 1 マスで消します。
**要素が更新されると作り直しになります。**読み取りが多く更新が少ない場合に向く型です。更新も頻繁なら別のデータ構造が要ります。
単調スタック — 「次に大きい要素」
各要素について「自分より右にある、最初に自分より大きい要素」を求めます。素直に書くと O(n²) です。
スタックに、まだ答えが決まっていない要素を積んでおきます。
function nextGreater(ys: number[]): number[] {
const out = new Array<number>(ys.length).fill(-1);
const stack: number[] = []; // 添字を積む。対応する値は下から上へ増えない
for (let i = 0; i < ys.length; i++) {
while (stack.length > 0 && ys[stack[stack.length - 1]] < ys[i]) {
out[stack.pop() as number] = ys[i]; // 積んであった要素の答えが今決まる
}
stack.push(i);
}
return out;
}
console.log(nextGreater([2, 1, 5, 3, 6, 4]).join(","));
// 5,5,6,6,-1,-1
2 と 1 の答えはどちらも 5、5 と 3 の答えはどちらも 6、6 と 4 には右に大きい要素がないので -1 です。
各要素はスタックに 1 回積まれて 1 回降ろされるだけなので、内側に while があっても全体で O(n) です。
**スタックの中身が単調 (この例では下から上へ増えない) に保たれるのが名前の由来です。**新しい要素が来たとき、それより小さい要素は「答えが今決まった」ので降ろせます。降ろした要素を二度と見ないのが O(n) の根拠です。
この型は「棒グラフの中で作れる最大の長方形」や「雨水がどれだけ溜まるか」といった、左右の高い壁を探す問題の土台になります。
判定の手順
O(n²) の二重ループを見つけたら、この順で当てます。
| 内側のループが何をしているか | 当たる型 | 適用条件 |
|---|---|---|
| 「この値と対になる値」を探している | ハッシュ (未ソート) / two pointer (ソート済み) | two pointer はソート済みであること |
| 連続した範囲の集計をやり直している | スライディングウィンドウ | 範囲の増減で条件が単調に変わる |
| 区間の合計を何度も聞いている | 累積和 | 要素の更新が少ない |
| 「自分より大きい / 小さい最初の要素」を探している | 単調スタック | 一方向の走査で答えが確定する |
**先に見るのは「内側のループが毎回ゼロからやり直しているか」です。**やり直していれば、前の結果を再利用できる余地があります。やり直していない (たとえば全組合せを本当に列挙している) なら、そもそも出力が O(n²) あるので落とせません。
**当てはまらないこともあります。**その場合は、そもそも O(n²) で足りる件数なのかを確かめてください。100 件なら 1 万回で、最適化する価値はありません。
よくある誤解
「内側に while があるから二重ループ」 — 走査の総回数で数えます。可変長ウィンドウも単調スタックも、内側の処理の合計が n 回に収まるので O(n) です。ループの見た目でなく、1 要素あたり何回触るかを数えてください。
「two pointer はソートしてから使えばよい」 — ソートに O(n log n) かかるので、O(n) の意味がなくなります。未ソートならハッシュが既定です。ソートするのは、順序そのものが答えに要るときだけです。
「累積和は常に速い」 — 更新が入るたびに O(n) で作り直しになります。読み取りと更新の比率で選びます。
「型を覚えれば当てはめられる」 — 適用条件のほうが本体です。可変長ウィンドウは単調性、two pointer はソート済み、単調スタックは一方向で確定すること。条件を確かめずに当てると、答えが静かに間違います。
確認問題
問 1. アクセスログから「連続する 5 分間のリクエスト数が最大の区間」を求める処理が、1 日ぶん (約 8 万件) で数十秒かかります。どう直しますか。
答え: 固定長のスライディングウィンドウにします。
遅い実装はおそらく、各時刻について「そこから 5 分間」を毎回数え直しています。1 区間あたりの件数を k とすると O(n × k) です。
窓を 1 つずらすと、出ていく件と入ってくる件しか変わりません。差分だけ更新すれば O(n) になります。
実装で注意するのは境界です。時刻でなく件数で窓を切ると、リクエストが疎な時間帯で 5 分を超えた範囲を数えてしまいます。窓は時刻で切り、左端は「右端の時刻 − 5 分」より古いものを外すという可変長の形にするのが正確です。この形でも lo は戻らないので O(n) のままです。
前提として、ログが時刻順に並んでいることが要ります。並んでいなければ先にソートが必要で、そこで O(n log n) かかります。
問 2. 商品の価格配列から「各商品について、右側にある最初のより高い商品の価格」を求めたい。素直に書くと二重ループです。どう落としますか。
答え: 単調スタックで O(n) にします。
まだ答えが決まっていない商品の添字をスタックに積みます。新しい商品の価格を見たとき、スタックの上から順に「その価格より安い」ものを降ろし、答えを今の価格に確定させます。
各商品はスタックに 1 回積まれ、1 回降ろされるだけです。内側に while があっても総回数は 2n に収まるので O(n) です。
**スタックが単調に保たれるのが動く理由です。**降ろす条件が「今の価格より安い」なので、残るものは常に今の価格以上、つまり上に行くほど安い並びになります。この性質があるから、途中で止めて残りを見なくてよいと判断できます。
同じ形で「左側にある最初のより高い商品」も求まります。走査の向きを逆にするだけです。両方を組み合わせると「その商品より高い商品に挟まれた区間」が出るので、価格帯の分析に使えます。
問 3. 「配列から、和が特定の値になる 2 要素を探す」処理を two pointer で書いたら、答えが見つからないケースがありました。何を確かめますか。
答え: 配列がソート済みかを確かめます。
two pointer が成り立つ根拠は、「和が小さいとき、左端はどの相手とも目標に届かないので捨てられる」という判断です。この判断は右端が現時点の最大であることに依存しています。ソートされていなければ右端は最大ではなく、捨ててよいという結論が出ません。
確かめ方は、入力が本当に昇順かを検査する 1 行を足すことです。降順に並んでいた、あるいは一部だけソートされていた、というのがよくある形です。
**未ソートならハッシュを使います。**1 回走査しながら「目標値 − 現在の値」が既出かを問い合わせる方法で、O(n) のままソートが要りません。two pointer をわざわざ使うためにソートすると O(n log n) になり、遅くなります。
**two pointer を選ぶのは、入力がもともとソート済みのときだけです。**データベースから ORDER BY 付きで取っている、時刻順のログである、といった場合が該当します。
まとめ
- 4 つの型に共通するのは**「内側のループのやり直しを、前の結果の再利用に置き換える」**こと
- two pointer — 両端から寄せる。
O(n)。ソート済みが条件 - スライディングウィンドウ — 出入りの差分だけ更新する。可変長では範囲の増減で条件が単調に変わることが条件
- 累積和 — 前計算
O(n)、以降 1 回O(1)。更新が少ないときに向く。先頭に 0 を置くと境界の場合分けが消える - 単調スタック — 各要素が 1 回積まれ 1 回降ろされるので
O(n)。降ろした要素を二度と見ないのが根拠 - **内側に
whileがあっても二重ループとは限らない。**走査の総回数で数える - **未ソートならハッシュが既定。**two pointer のためにソートすると全体が
O(n log n)に落ちる - **型より適用条件が本体。**条件を確かめずに当てると答えが静かに間違う
- 100 件程度なら
O(n²)で足りる。落とす前に件数を確かめる