スライディングウィンドウパターン

中級

カテゴリ: hash-tables

概要

スライディングウィンドウは、配列やリスト上で「窓」のように一定範囲の要素を連続的に処理するテクニックです。窓を左から右へスライドさせながら、各窓内の要素に対して計算を行います。このパターンを使うと、部分配列や部分文字列に関する問題を効率的に解くことができ、二重ループを使わずに線形時間（O(n)）で解決できることが多いです。

コードテンプレート

Java

Python

- 固定サイズの窓
int windowSize = k;
int result = 0;
int windowSum = 0;

// 最初の窓を計算
for (int i = 0; i < windowSize; i++) {
    windowSum += array[i];
}
result = windowSum;

// 窓をスライドさせる
for (int i = windowSize; i < array.length; i++) {
    windowSum = windowSum - array[i - windowSize] + array[i]; // 左端を削除し、右端を追加
    result = Math.max(result, windowSum); // 必要に応じて結果を更新
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

連続した部分配列部分文字列最大の和最小の長さ窓スライド連続した要素サブアレイストリーム処理移動平均連続したk個最長の部分列最短の部分列重複なし条件を満たす最小範囲

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
最大部分配列の和（Maximum Subarray Sum）: 合計が最大となる連続した部分配列を見つける
2
最小サイズの部分配列の和（Minimum Size Subarray Sum）: 合計が特定の値以上となる最小の連続した部分配列を見つける
3
最長の部分文字列（Longest Substring Without Repeating Characters）: 重複する文字を含まない最長の部分文字列を見つける
4
文字列の順列（Permutation in String）: ある文字列の順列が別の文字列の部分文字列として存在するかを判定する

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

中

最小サイズ部分配列の和

正の整数の配列 nums と正の整数 target が与えられたとき、和が target 以上になる連続部分配列の最小長を返してください。そのような部分配列が存在しない場合は、0 を返します。...

中

重複のない最長部分文字列

文字列 s が与えられたとき、重複する文字を含まない最長の部分文字列の長さを返してください。...

中

最長の繰り返し文字置換

文字列 s と整数 k が与えられます。任意の文字を別の文字に最大 k 回置き換えることができます。この操作を行った後、同じ文字の連続する最長の部分文字列の長さを求めてください。...