滑动窗口

滑动窗口是 C 语言中处理数组 / 字符串子问题的高效算法思想，核心是通过双指针（ left / right ） 维护一个连续的 “窗口”，并通过移动指针调整窗口范围，避免重复计算，将时间复杂度从暴力解法的 O (n²) 优化至 O (n)。适用于子串 / 子数组的求和、查找、去重等场景。

一、滑动窗口核心概念

1. 核心思想
   • 窗口：数组 / 字符串中一段连续的子区间，用 left（左边界）和 right（右边界）标记。
   • 滑动：通过移动 right 扩张窗口、移动 left 收缩窗口，动态调整窗口范围。
   • 优势：复用前一个窗口的计算结果（如总和、字符状态），避免重复遍历子区间，提升效率。
2. 适用场景
   • 子串 / 子数组长度固定（如 “长度为 k 的最大子数组和”）。
   • 子串 / 子数组满足特定条件（如 “无重复字符的最长子串”“和大于等于 target 的最短子数组”）。

结合上述使用场景，我们将滑动窗口分为定长滑动窗口和不定长滑动窗口两大类。

二、定长滑动窗口

1. 特点

1. 窗口大小 k 固定，right 与 left 同步移动（right 移动后，left 随之移动，保持窗口长度不变）。
2. 核心操作：窗口扩张时加入新元素，窗口滑动时移除左边界元素的影响。

2. 实现步骤

1. 初始化：left=0，窗口状态变量（如总和、计数），结果变量（如最大和）。
2. 扩张窗口：移动 right，将当前元素纳入窗口，更新状态变量。
3. 窗口成型：当 right - left + 1 == k（窗口长度达标）时：
   计算当前窗口结果，更新全局最优解。
4. 收缩窗口：移除 left 元素的影响（如总和减去 nums[left]），left 右移。
5. 待窗口成型后，扩张与收缩窗口并行，直到 right 遍历完数组 / 字符串。

文字版看懂相对来说较难，接下来将结合题目具体说明滑动窗口的使用。

3. 例子

以力扣1456为例：

首先，这个窗口的大小为 k ，所以用一个大小为 k 的滑动窗口遍历字符串，统计并比较该窗口中元音字母的数量，得出最大值。

代码示例：

// 定义宏函数MAX：返回两个整数a和b中的较大值，括号确保表达式优先级正确
#define MAX(a,b) ((a) > (b) ? (a) : (b))

int maxVowels(char* s, int k) {
    int ans = 0;  // 存储最终结果：元音字母的最大个数
    int cur = 0;  // 存储当前窗口内元音字母的个数（窗口状态变量）
    char* a = "aeiou";  // 元音字母集合，用于判断字符是否为元音

    // 遍历字符串s，right指针（i）负责扩张窗口，从左到右扫描每个字符
    for (int i = 0; s[i]; i++) {
        // 检查当前字符s[i]是否为元音（strchr在a中查找s[i]）
        if (strchr(a, s[i])) {
            cur++;  // 若是元音，当前窗口的元音计数+1
        }

        // 计算当前窗口的左边界：i为右边界，窗口长度为k → 左边界 = 右边界 - k + 1
        int left = i - k + 1;

        // 窗口未成型（左边界为负）：此时窗口长度不足k，无需计算结果，继续扩张
        if (left < 0) {
            continue;
        }

        // 窗口成型（长度达到k）：更新最大元音个数（取当前最大值和当前窗口计数的较大值）
        ans = MAX(ans, cur);

        // 窗口即将向右滑动，移除左边界元素（s[left]）对当前窗口的影响
        char out = s[left];
        // 若移除的左边界元素是元音，当前窗口的元音计数-1
        if (strchr(a, out)) {
            cur--;
        }
    }

    // 返回长度为k的子串中元音字母的最大个数
    return ans;
}

三、不定长滑动窗口

1. 特点

1. 窗口大小不固定，right 负责扩张窗口（探索新元素），left 负责收缩窗口（满足特定条件时）。
2. 核心操作：根据问题目标（最长 / 最短窗口），动态调整 left 的位置。

2. 实现步骤

1. 找满足最长条件的窗口

   • 初始化：left=0，结果变量（最大长度），状态记录容器（如哈希表 / 数组）。
   • 扩张窗口：移动 right，遍历每个元素。
   • 校验条件：若当前元素破坏窗口规则（如重复），移动 left 收缩窗口，直到规则满足。
   • 更新状态：记录当前元素的位置 / 计数。
   • 计算窗口长度，更新全局最大长度。
   • 重复至 right 遍历结束。

2. 找满足最短条件的窗口

   • 初始化：left=0，结果变量（最小长度，初始为无穷大），状态变量（如总和）。
   • 扩张窗口：移动 right，将元素纳入窗口，更新状态变量。
   • 校验条件：若窗口满足条件（如总和≥target），尝试收缩 left，更新最小长度。
   • 重复步骤，直到 right 遍历结束。

3. 示例

以力扣3为例

代码示例：

int lengthOfLongestSubstring(char* s) {
    // cnt[128]：计数数组，存储当前窗口内每个ASCII字符的出现次数
    // 索引对应ASCII码值（0-127），值为该字符在窗口内的出现次数，初始化为0
    int cnt[128] = {0};
    int left = 0;          // 滑动窗口左边界指针（收缩窗口时移动）
    int ans = 0;           // 存储最终结果：最长无重复子串的长度
    int len = strlen(s);   // 字符串长度

    // 循环遍历字符串，right作为窗口右边界指针（扩张窗口时移动）
    for (int right = 0; right < len; right++) {
        // 1. 扩张窗口：将当前右边界字符s[right]纳入窗口，其计数+1
        cnt[s[right]]++;

        // 2. 校验窗口规则：若当前字符在窗口内出现次数>1（存在重复），则收缩左边界
        // 用while循环确保收缩后，窗口内无重复字符（直到当前字符计数≤1）
        while (cnt[s[right]] > 1) {
            cnt[s[left]]--;  // 移除左边界字符的计数（从窗口中排除）
            left++;          // 左边界右移，收缩窗口
        }

        // 3. 计算当前窗口长度（right - left + 1），更新最长长度ans
        int length = right - left + 1;
        ans = ans > length ? ans : length;  // 取当前最长长度和新窗口长度的较大值
    }

    // 返回无重复字符的最长子串长度
    return ans;
}

四、总结

1. 定长 vs 不定长窗口对比

特性	定长滑动窗口	不定长滑动窗口
窗口大小	固定（k）	动态调整（扩张 / 收缩）
指针移动	left 与 right 同步移动	right 扩张，left 按需收缩
适用场景	固定长度的子串 / 子数组问题	满足条件的最长 / 最短子串问题
核心操作	加入右元素 → 移除左元素	扩张 → 校验 → 收缩

2. 核心优化点
   • 复用窗口状态：避免每次重新计算子区间的总和 / 字符状态，降低时间复杂度。
   • 边界处理：注意 left 和 right 的取值范围，避免数组越界。
   • 状态容器：根据场景选择哈希表（字符 / 数字去重）、数组（ASCII 字符）等，提升查询效率。
3. 注意事项
   • 定长窗口：需先让窗口成型（right - left +1 ==k）再计算结果。
   • 不定长窗口：收缩 left 时用 while 循环（而非 if），确保窗口满足最优条件。
   • 特殊情况：如无满足条件的子数组，需返回默认值。