sko.kr
  • ホーム
  • ブログ
  • アルゴリズム - 1. スライディングウィンドウ（固定サイズ）

アルゴリズム - 1. スライディングウィンドウ（固定サイズ）

algorithmssliding-windowarraysoptimizationtwo-pointers
By sko•9/27/2025•4 min read

固定サイズスライディングウィンドウをいつ使うか

特定のサイズの最適な連続部分配列を見つける必要がある場合に、固定サイズスライディングウィンドウを使用します。サイズの制約は限定的に見えますが、このパターンは頻繁に現れます：

  • 最大/最小和 k個の連続する要素の（典型的な使用例）
  • 平均 k個の連続する要素の
  • パターンマッチング 固定長パターンによる（アナグラムを見つけるなど）
  • ローリングハッシュ 部分文字列マッチングのための
  • 時系列分析 固定時間ウィンドウによる（例：7日移動平均）
  • サイズkのすべての部分配列の分析を必要とする任意の問題

例題

K要素の最大和：日次売上収益 [100, 200, 300, 400, 100, 200, 50] が与えられ、最も高い総収益を持つ3連続日の期間を見つけます。

  • 日[0-2]：100 + 200 + 300 = 600
  • 日[1-3]：200 + 300 + 400 = 900 ✓ 最良期間
  • 日[2-4]：300 + 400 + 100 = 800
  • 日[3-5]：400 + 100 + 200 = 700
  • 日[4-6]：100 + 200 + 50 = 350

答え：日1-3が最高総収益$900を持ちました。

最も重要な洞察

重複する計算を再利用する - サイズkの隣接するウィンドウはk-1個の共通要素を共有し、出ていく1つの要素と入ってくる1つの要素だけが異なるため、すべてを再計算する代わりにこれら2つの変更だけを更新し、O(n*k)ではなくO(n)の複雑さを実現します。

覚え書き：このアルゴリズムの天才性は、隣接するウィンドウが大幅に重複することを認識している点にあります。サイズ3のウィンドウの場合、それを前進させることは2つの要素が同じままであることを意味し、最も左の要素が出て、新しい最も右の要素が入るだけです。最初から再計算する代わりに、実行中の状態を維持して段階的に更新します。1つの減算、1つの加算 - それが次のウィンドウに「スライド」するのに必要なすべてです。

決定フレームワーク

ウィンドウのすべてのスライドで、2つの操作を実行します：

  • ウィンドウから出る要素の貢献を削除する（左側）
  • ウィンドウに入る要素の貢献を追加する（右側）

コード

// 注意：while文ではなくfor文を使用する理由：
// - 固定サイズスライディングウィンドウでは、各要素を正確に1回処理する
// - 右ポインタは常に1ずつ増加する
// - for文の方がクリーンでright++を忘れることを防ぐ

// ちょうどサイズkの固定ウィンドウ
// すべての可能なkサイズウィンドウを調べる必要がある
function maxSumOfK(nums: number[], k: number): number {
  if (nums.length < k) return -1;

  let windowSum = 0;
  let maxSum = -Infinity;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // 現在の要素をウィンドウに追加
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // 決定フレームワーク：ちょうどサイズkのウィンドウを維持
    const windowSize = right - left + 1;
    // ウィンドウがちょうどkの時に処理し、その後スライドする
    if (windowSize === k) {
      maxSum = Math.max(maxSum, windowSum);
      // 次の反復のためにウィンドウをスライド
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

  return maxSum;
}

// 最大サイズkのウィンドウ
// 「k距離以内の重複」は、kを超えないウィンドウが必要であることを意味する
function hasDuplicateWithinK(nums: number[], k: number): boolean {
  const window = new Set<number>();
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // 決定フレームワーク：ウィンドウサイズ <= kを維持
    // なぜ上記と異なるのか？「k距離以内」は最大k要素離れていることを意味する
    // そのため、kまで成長し、その後サイズkでスライドする固定ウィンドウを維持する
    const windowSize = right - left + 1;
    const windowExceedsK = windowSize > k;
    if (windowExceedsK) {
      const elementLeavingWindow = nums[left];
      window.delete(elementLeavingWindow);
      left++;
    }

    // 現在のウィンドウで重複をチェック
    const currentElement = nums[right];
    const isDuplicate = window.has(currentElement);

    if (isDuplicate) {
      return true;
    }

    // 現在の要素をウィンドウに追加
    window.add(currentElement);
  }

  return false;
}

疑問解決

よくある疑問：「なぜウィンドウの和を追跡するのか？ネストしたループを使って各k要素のウィンドウを別々に合計できないのか？」

ネストしたループで十分だと思う理由

[100, 200, 300, 400, 100, 200, 50]でk=3の最大和を見つけることを考えてみましょう：

  • 「開始位置に外側ループ、k要素を合計する内側ループを使える」
  • 「各開始位置iについて、iからi+k-1まで合計する」
  • 「たった3要素なので、内側ループは小さい」
  • 「コードがより直感的 - 何が合計されているかが正確に見える」

この考えが非効率的である理由

重要な気づき：ネストしたループは同じ要素を繰り返し再計算します！

k=3で[100, 200, 300, 400, 100, 200, 50]をトレースしてみましょう：

ネストしたループアプローチ（O(n*k)）：
ウィンドウ[0-2]：100 + 200 + 300 = 600    （3回の加算）
ウィンドウ[1-3]：200 + 300 + 400 = 900    （3回の加算）
ウィンドウ[2-4]：300 + 400 + 100 = 800    （3回の加算）
ウィンドウ[3-5]：400 + 100 + 200 = 700    （3回の加算）
ウィンドウ[4-6]：100 + 200 + 50 = 350     （3回の加算）
合計：15回の加算

スライディングウィンドウ（O(n)）：
初期[0-2]：100 + 200 + 300 = 600   （3回の加算）
[1-3]にスライド：600 - 100 + 400 = 900  （1回の減算、1回の加算）
[2-4]にスライド：900 - 200 + 100 = 800  （1回の減算、1回の加算）
[3-5]にスライド：800 - 300 + 200 = 700  （1回の減算、1回の加算）
[4-6]にスライド：700 - 400 + 50 = 350   （1回の減算、1回の加算）
合計：3回の加算 + 4回の減算 + 4回の加算 = 11操作

300などの要素がネストしたループでは3回加算されるが、スライディングウィンドウでは1回だけであることに注意してください！

具体例：スケーリング問題

k=1000で10,000要素の配列の最大和を見つける場合：

ネストしたループ：

  • 各ウィンドウ：1000要素を合計
  • 総ウィンドウ数：9001
  • 総加算回数：9,001,000

スライディングウィンドウ：

  • 初期ウィンドウ：1000回の加算
  • 各スライド：1回の減算 + 1回の加算
  • 総操作数：1000 + (9000 × 2) = 19,000
  • 474倍高速！

最適化が重要である理由

スライディングウィンドウ技法は：

  • 重複する計算を再利用する（k-1要素は同じまま）
  • 各要素は正確に1回加算され、正確に1回減算される
  • 同じ要素の冗長な計算なし
  • O(n×k)のネストしたループ解法をO(n)のスライディングウィンドウに変換

重要な洞察：ウィンドウを1位置移動させる際、たった2つの要素が変更される（1つが去り、1つが入る）ので、なぜすべてを再計算するのでしょうか？

← Back to Blog