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

アルゴリズム - 2. スライディングウィンドウ（可変サイズ）

algorithmssliding-windowtwo-pointersoptimizationarraysstrings
By sko•9/28/2025•5 min read

可変サイズスライディングウィンドウを使用するタイミング

サイズが事前に決定されていない最適な連続サブ配列を見つける必要がある場合に、可変サイズのスライディングウィンドウを使用します。このアルゴリズムは、サイズを最適化しながら特定の条件を維持するために、ウィンドウの境界を動的に調整します。

  • 合計 ≥ ターゲットの最小/最大サイズのサブ配列（典型的な使用例）
  • 重複文字のない最長部分文字列
  • 必要なすべての文字を含む最小ウィンドウ部分文字列
  • 特定のプロパティを持つサブ配列の数
  • 種類の制約がある最大アイテムコレクション（例：フルーツバスケット）
  • 条件を維持するためにウィンドウサイズが適応するあらゆる問題

例題

最小の買い物袋: アイテムの重量 [2, 3, 1, 2, 4, 3] が与えられ、少なくとも7kgの合計が必要な場合、選ぶべき連続したアイテムの最小数は？

  • アイテム [0-3]: 2 + 3 + 1 + 2 = 8 kg ✓（4アイテム）
  • アイテム [1-4]: 3 + 1 + 2 + 4 = 10 kg ✓（4アイテム）
  • アイテム [2-4]: 1 + 2 + 4 = 7 kg ✓（3アイテム）
  • アイテム [4-5]: 4 + 3 = 7 kg ✓（2アイテム）← ベスト！

答え: 2アイテム（位置4-5のアイテム）。

最も重要な洞察

可能性を探るためにウィンドウを展開し、条件が満たされたら左から縮小する - この展開・縮小のダンスにより、すべてのO(n²)の可能性をチェックすることなく、最適なサイズを見つけるために境界を体系的に調整することで、すべての有効なウィンドウを確実に検証できます。

メンタルノート: このアルゴリズムの天才的な点は、「有効なウィンドウ不変条件」を維持することです。各ステップで、「このウィンドウを縮小しても条件を満たせるか？」という単純な決定だけを行います。この単純な決定により、最適なウィンドウが自動的に見つかります。すべての可能なウィンドウをチェックする代わりに、新しい要素を含めるように展開し、その後、各位置で終わる最小の有効なウィンドウを見つけるために貪欲に縮小します。

決定フレームワーク

すべての位置で、アルゴリズムは2つの順次的な決定を行います：

  • 展開: 常に現在の要素を含める（右ポインタを移動）
  • 縮小: 条件が満たされている間、左から削除して最小化を試みる

コード

// 合計 >= ターゲットの最小サイズのサブ配列を見つける
// ネストされたループがありますが、O(n)時間 - 各要素は最大2回訪問される
function shortestSubarray(nums, target) {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;

  for (let right = 0; right < nums.length; right++) {
    // ステップ1: 展開 - 常に現在の要素を含める
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // 決定フレームワーク: 縮小してもまだ条件を満たせるか？
    // 任意の有効なウィンドウではなく、最適なウィンドウを見つけるためにwhile（ifではない）を使用
    while (windowSum >= target) {
      // 現在のウィンドウは条件を満たしている、最小の場合は記録
      const currentWindowSize = right - left + 1;
      minLength = Math.min(minLength, currentWindowSize);

      // 左から縮小してさらに小さい有効なウィンドウを見つけようとする
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

  return minLength === Infinity ? 0 : minLength;
}

// 最大k個の異なる文字を持つ最長部分文字列
// 問題: 最大k個の異なる文字を含む最長部分文字列を見つける
// 例: k=2の"eceaba" → "eceab"には3文字 ✗、"eceba"には3文字 ✗、"ece"には2文字 ✓
function longestSubstringKDistinct(s, k) {
  const charFrequency = new Map(); // ウィンドウ内の各文字のカウントを追跡
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    // 展開: ウィンドウに文字を追加
    const charEntering = s[right];
    charFrequency.set(charEntering, (charFrequency.get(charEntering) || 0) + 1);

    // 決定フレームワーク: k個を超える異なる文字がある場合は左から縮小
    // なぜ右からではなく左から縮小するのか？理由：
    // 1. すべての位置を右境界として体系的に試している
    // 2. 各右位置について、最も左の有効な位置を見つける
    // 3. これによりすべての可能なウィンドウをチェックすることが保証される（下記の疑問バスター参照）
    while (charFrequency.size > k) {
      const charLeaving = s[left];
      const count = charFrequency.get(charLeaving);

      // ウィンドウから離れる文字の頻度を減らす
      if (count === 1) {
        // これが最後の出現、マップから削除
        charFrequency.delete(charLeaving);
      } else {
        // ウィンドウにはまだ出現がある
        charFrequency.set(charLeaving, count - 1);
      }
      left++;
    }

    // ここでウィンドウは有効（≤ k個の異なる文字）、最大値を更新
    const currentWindowSize = right - left + 1;
    maxLength = Math.max(maxLength, currentWindowSize);
  }

  return maxLength;
}

疑問バスター

一般的な疑問: 「なぜ左からしか縮小しないのか？右から削除した方が良い結果が得られるかもしれないのでは？」

右から削除した方が良いと思う理由

これは自然な懸念です！ウィンドウに異なる文字が多すぎる場合、次のように考えるかもしれません：

  • 「追加したばかりの文字（右側）が問題なのでは？」
  • 「右から削除すれば、より長い有効なウィンドウが維持できるのでは？」
  • 「両方向を試して、より良い方を選ぶべきでは？」
  • 「常に左から縮小するという貪欲な選択は恣意的に見える」

例えば、文字列"abcba"でk=2の場合：

  • インデックス2（文字'c'）に達すると、ウィンドウは3つの異なる文字を持つ"abc"になる
  • 左から削除すると"bc"（長さ2）
  • でも右から削除すると"ab"（これも長さ2）？
  • 両方のオプションを検討すべきでは？

この考えが間違っている理由

重要な認識: 右から削除する必要はありません。なぜなら、そのオプションは将来の反復で自然に探索されるからです！

決定的な洞察は次のとおりです：**アルゴリズムは体系的にすべての位置を右境界として試します。**したがって、右から削除する方が良いウィンドウが得られる場合、その位置に達したときにそれを発見します。

"abcba"とk=2でこれを証明しましょう：

right=0: ウィンドウ ["a"]、1つの異なる文字、有効 ✓
right=1: ウィンドウ ["ab"]、2つの異なる文字、有効 ✓、maxLen=2
right=2: ウィンドウ ["abc"]、3つの異なる文字、無効 ✗
  - 左から縮小: ["bc"]、2つの異なる文字、有効 ✓
right=3: ウィンドウ ["bcb"]、2つの異なる文字、有効 ✓、maxLen=3
right=4: ウィンドウ ["bcba"]、3つの異なる文字、無効 ✗
  - 縮小: ["cba"]、3つの異なる文字、まだ無効 ✗
  - 縮小: ["ba"]、2つの異なる文字、有効 ✓

重要な洞察: "abc"があり、左から削除して"bc"を得たとき、"ab"を見逃したと心配しました。しかし注意してください：

  • ウィンドウ"ab"はright=1のときにすでに評価されていました！
  • その時点でその長さ（2）を記録しました
  • 後で、長さ3の"bcb"を見つけました。これはより良いものです

すべての可能なウィンドウが評価されます、なぜなら：

  1. 位置1で終わるウィンドウ：["a"]、["ab"]を試した
  2. 位置2で終わるウィンドウ：["abc"]→["bc"]、["c"]を試した
  3. 位置3で終わるウィンドウ：["bcb"]、["cb"]、["b"]を試した
  4. 以下同様...

アルゴリズムはウィンドウを見逃しません - 体系的にすべてを評価します！

具体的な証明：左から縮小するだけで十分な理由

次のように考えてください：最適なウィンドウ[i, j]がある場合、アルゴリズムはそれを見つけます：

  1. 右ポインタがjに達したとき: ある左位置からjまでのすべての要素を持つ
  2. whileループが縮小する: ウィンドウが有効になるまで左ポインタを右に移動
  3. iまたはその前で停止する: [i, j]が有効なので、縮小は位置iまでに停止
  4. このウィンドウを記録する: これまでに見た中で最高の場合、最大値を更新

右から削除することが冗長である理由

位置right=5でウィンドウ[2,3,4,5]があり、無効だと想像してください。「[2,3,4]が[3,4,5]よりも良いかもしれない」と考えるかもしれません。

しかし、[2,3,4]をチェックする必要がない理由は次のとおりです：

  • rightが位置4にあったとき、すでに[2,3,4]をチェックしました！
  • [2,3,4]が有効で良かった場合、その時点で記録しました
  • 今、位置5で、5で終わる最高のウィンドウを見つけています
  • 次の反復（right=6）で、6で終わる最高のウィンドウを見つけます

アルゴリズムの保証: 配列内のすべての可能なウィンドウについて、次の瞬間があります：

  • 右ポインタがウィンドウの終了位置にある
  • 左ポインタがウィンドウの開始位置に（またはそれを超えて）移動される
  • したがって、すべてのウィンドウが正確に1回評価される

これが、O(n²)が必要に見えるにもかかわらず、アルゴリズムがO(n)である理由です - バックトラックや以前の決定の再検討をする必要がありません。

← Back to Blog