1. 手法の概要
連続する部分配列や部分文字列を対象とした最適化問題において、滑动窗口法（Sliding Window）は極めて有効な戦略です。この手法は、データ上の連続する区間を仮想的な「窗口」として定義し、その区間を滑动させながら特定の条件を満たす解を探索します。全探索では O(N^2) となるようなケースでも、窗口の拡大・縮小を適切に制御することで、計算量を O(N) レベルに抑えることが可能です。
主に「条件を満たす最小（または最大）の連続区間を見つけよ」といった問題に適用されます。区間が連続している性質を利用し、既存の計算結果を再利用することで探索空間を剪枝し、重複計算を回避するのが特徴です。
2. 基本的な仕組み
滑动窗口アルゴリズムの基本的なフローは、二本のポインタ（始点と終点）を用いて区間を管理することにあります。
- 始点（left）と終点（right）を初期位置に設定し、閉区間 [left, right] を窗口とみなします。
- 終点ポインタを右へ移動させ、窗口を拡大します。窗口内のデータが条件を満たす状態になるまで続けます。
- 条件を満たした時点で、今度は始点ポインタを右へ移動させ、窗口を縮小します。条件を満たさなくなる直前まで縮小し、その過程で最適解を更新します。
- 終点ポインタがデータの末尾に到達するまで、上記の拡大・縮小を繰り返します。
このプロセスにより、「条件を満たす解」を見つけ（拡大）、その解を最適化し（縮小）、最終的に全体での最適解を得ることができます。
3. 実装パターンと具体例
以下に、代表的な問題における実装アプローチを示します。各例では、変数名やループ構造を工夫し、可読性と保守性を高めています。
3.1. 和が目標値以上となる最小部分配列 (LeetCode 209)
正整数の配列から、総和が指定値以上になる最小の連続部分配列の長さを求める問題です。
def find_min_subarray_length(target_sum: int, numbers: list) -> int:
current_total = 0
start_idx = 0
min_length = float('inf')
for end_idx in range(len(numbers)):
current_total += numbers[end_idx]
# 条件を満たしている間、窗口を縮小
while current_total >= target_sum:
current_len = end_idx - start_idx + 1
if current_len < min_length:
min_length = current_len
current_total -= numbers[start_idx]
start_idx += 1
return 0 if min_length == float('inf') else min_length
この実装では、終点ポインタをループで動かし、条件成立時に内部ループで始点ポインタを動かす構造にしています。
3.2. 最小覆盖部分文字列 (LeetCode 76)
文字列 S の中に、文字列 T のすべての文字を含む最小の部分文字列を見つける問題です。ハッシュマップを用いて文字の出現頻度を管理します。
def min_window_substring(source: str, target: str) -> str:
if not source or not target:
return ""
from collections import defaultdict
target_counts = defaultdict(int)
for char in target:
target_counts[char] += 1
required_chars = len(target_counts)
formed_chars = 0
window_counts = defaultdict(int)
left, right = 0, 0
min_len = float('inf')
result_indices = (0, 0)
while right < len(source):
char = source[right]
window_counts[char] += 1
if char in target_counts and window_counts[char] == target_counts[char]:
formed_chars += 1
# 条件を満たしている間、窗口を縮小
while left <= right and formed_chars == required_chars:
char = source[left]
if right - left + 1 < min_len:
min_len = right - left + 1
result_indices = (left, right)
window_counts[char] -= 1
if char in target_counts and window_counts[char] < target_counts[char]:
formed_chars -= 1
left += 1
right += 1
return "" if min_len == float('inf') else source[result_indices[0]:result_indices[1] + 1]
ここでは、必要な文字種類数と、窗口内で条件を満たしている文字種類数を比較することで、条件判定を効率化しています。
3.3. 重複文字のない最長部分文字列 (LeetCode 3)
文字列の中で、重複する文字を含まない最長の部分文字列の長さを求めます。辞書を用いて文字の直近のインデックスを記録します。
def length_of_longest_unique_substring(text: str) -> int:
char_index_map = {}
max_len = 0
start = 0
for end in range(len(text)):
current_char = text[end]
# 重複が見つかった場合、始点を更新
if current_char in char_index_map and char_index_map[current_char] >= start:
start = char_index_map[current_char] + 1
char_index_map[current_char] = end
max_len = max(max_len, end - start + 1)
return max_len
set を使う方法もありますが、インデックスを直接記録することで、始点ポインタのジャンプ処理を O(1) で行えるように优化しています。
3.4. 最大連続 1 の个数 (LeetCode 1004)
配列内の 0 を最大 K 個まで 1 に反転させたとき、連続する 1 の最大長を求める問題です。窗口内の 0 の個数をカウントします。
def longest_ones_with_flips(data: list, max_flips: int) -> int:
left = 0
zero_count = 0
max_length = 0
for right in range(len(data)):
if data[right] == 0:
zero_count += 1
# 許容範囲を超えた場合、左側から縮小
while zero_count > max_flips:
if data[left] == 0:
zero_count -= 1
left += 1
max_length = max(max_length, right - left + 1)
return max_length
このアプローチでは、窗口内に含まれる 0 の数が K を超えないように制御 while ループを回しています。
3.5. 文字置換による最長繰り返し文字列 (LeetCode 424)
最大 K 回の文字置換を行って得られる、同じ文字で構成された最長部分文字列の長さです。窗口内の最頻文字の出現回数を維持します。
def character_replacement_solution(input_str: str, k: int) -> int:
freq_map = [0] * 26
left = 0
max_freq = 0
result = 0
for right in range(len(input_str)):
index = ord(input_str[right]) - ord('A')
freq_map[index] += 1
max_freq = max(max_freq, freq_map[index])
# 窗口サイズ - 最頻文字数 > k なら条件不满足
if (right - left + 1) - max_freq > k:
left_index = ord(input_str[left]) - ord('A')
freq_map[left_index] -= 1
left += 1
result = max(result, right - left + 1)
return result
ここで重要なのは、max_freq を縮小時に更新しない点です。最大長を更新することが目的であるため、窗口が縮小しても以前の最大記録を保持し続けることで、結果的に正しい最大長を得ることができます。