スライディングウィンドウの適用条件

スライディングウィンドウは、配列や文字列における連続した部分列に関する問題に有効です。特に、以下のような要件を持つ問題に適しています：

• 部分配列・部分文字列の最小/最大長を求める
• 特定の条件を満たす最短/最長の連続要素を探索する
• 許容誤差（例：最大k個の0を1に変換）付きでの最適解を求める

基本的な実装手順

1. 管理対象の状態変数を定義（例：合計値、ハッシュマップ、カウンタなど）
2. ウィンドウの両端を初期化（左端 start = 0、右端 end をループで進める）
3. 右端を拡張し、状態を更新
4. 条件に基づき左端を調整：
   • 固定長の場合：ウィンドウサイズが指定値に達したら左端を1つ進める
   • 可変長の場合：条件を満たさなくなるまで左端を縮小（whileループ使用）
5. 最終結果を返却

可変長ウィンドウの代表例

最小合計部分配列（LeetCode 209）

正整数配列と目標値 target が与えられ、合計が target 以上となる最短の連続部分配列の長さを求める。

function minSubArrayLen(target, nums) {
    let minLength = Infinity;
    let windowSum = 0;
    let left = 0;

    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];

        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }

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

最小被覆部分文字列（LeetCode 76）

文字列 s の中から、文字列 t のすべての文字を含む最短の部分文字列を返す。

function minWindow(s, t) {
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }

    let formed = 0;
    const window = new Map();
    let result = "";
    let minLen = Infinity;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        if (need.has(char)) {
            window.set(char, (window.get(char) || 0) + 1);
            if (window.get(char) === need.get(char)) {
                formed++;
            }
        }

        while (formed === need.size) {
            const currentLen = right - left + 1;
            if (currentLen < minLen) {
                minLen = currentLen;
                result = s.substring(left, right + 1);
            }

            const leftChar = s[left];
            if (window.has(leftChar)) {
                window.set(leftChar, window.get(leftChar) - 1);
                if (window.get(leftChar) < need.get(leftChar)) {
                    formed--;
                }
            }
            left++;
        }
    }

    return result;
}

重複なし最長部分文字列（LeetCode 3）

文字列内で重複文字を含まない最長部分文字列の長さを求める。

function lengthOfLongestSubstring(s) {
    const seen = new Set();
    let maxLength = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }
        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

最大連続1の個数（LeetCode 485）

バイナリ配列において、連続する 1 の最大個数を求める。

function findMaxConsecutiveOnes(nums) {
    let current = 0;
    let maxCount = 0;

    for (const num of nums) {
        if (num === 1) {
            current++;
            maxCount = Math.max(maxCount, current);
        } else {
            current = 0;
        }
    }

    return maxCount;
}

近接重複要素の検出（LeetCode 219）

配列中に同じ値を持つ要素が存在し、そのインデックス差が k 以下であるか判定する。

function containsNearbyDuplicate(nums, k) {
    const window = new Set();
    let left = 0;

    for (let right = 0; right < nums.length; right++) {
        if (window.has(nums[right])) {
            return true;
        }
        window.add(nums[right]);

        if (right - left + 1 > k) {
            window.delete(nums[left]);
            left++;
        }
    }

    return false;
}

k個の0を反転可能な最大連続1（LeetCode 1004）

最大 k 個の 0 を 1 に変更できるとき、得られる最長の連続1の長さを求める。

function longestOnes(nums, k) {
    let zeroCount = 0;
    let maxLength = 0;
    let left = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            zeroCount++;
        }

        while (zeroCount > k) {
            if (nums[left] === 0) {
                zeroCount--;
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}