02 固定长度滑动窗口：模板推导与三题精讲

固定长度滑动窗口：模板推导与三题精讲

摘要

固定长度的滑动窗口是所有滑动窗口变体中最基础的一类，理解好它是攻克可变窗口的前提。本文围绕三道递进难度的题目展开：LeetCode 643（子数组最大平均数，纯加减维护）、LeetCode 1343（大小为 K 且平均值 ≥ 阈值的子数组数目，计数逻辑）、LeetCode 567（字符串的排列，字符计数+匹配检查）。通过这三题，系统推导固定窗口的通用模板，并深度讲解”进窗/出窗”操作的对称性、字符频率数组的高效使用，以及面试中极易踩坑的”初始化方式”问题。

---

第 1 章 固定窗口的本质：平移中的不变性

1.1 固定窗口解决了什么问题

固定长度窗口的使用场景是：题目明确要求考察长度恰好为 $k$ 的子数组（或子字符串），而不是”至少”或”至多”某个长度。这类问题有一个天然的优势：窗口大小是确定的，每次移动恰好”进一个、出一个”，状态更新的对称性非常强。

典型问题：

• 长度为 $k$ 的子数组的最大/最小/平均值
• 长度为 $k$ 的子字符串中，满足某种字符分布的子串个数
• 长度为 $k$ 的滑动窗口内的最大值序列

1.2 “进出对称”：固定窗口最优美的性质

固定窗口每次移动时，有一个非常优美的对称性：进入窗口的元素和离开窗口的元素恰好是一个一对，“一进一出”，窗口大小恒定不变。

初始窗口：[a₀, a₁, ..., aₖ₋₁]        长度 k
移动一步：     [a₁, a₂, ..., aₖ]       长度 k，a₀ 出，aₖ 进
移动两步：         [a₂, a₃, ..., aₖ₊₁] 长度 k，a₁ 出，aₖ₊₁ 进

这个对称性意味着：窗口状态的更新必须是”可撤销”的。进窗的操作有对应的出窗反操作：

• 进窗：sum += num；出窗：sum -= num（加减互逆 ✅）
• 进窗：count[c]++；出窗：count[c]--（增减互逆 ✅）
• 进窗：max = Math.max(max, num)；出窗：??? 不可逆 ❌

最后这个场景——维护窗口最大值——是固定窗口的难点，需要单调队列，将在第 07 篇专门讨论。

1.3 固定窗口通用模板

// 固定窗口通用模板（以数组为例，窗口大小为 k）
int maxResult(int[] nums, int k) {
    int n = nums.length;
    int answer = /* 初始值 */;
 
    // 阶段一：初始化，填满第一个窗口 [0, k-1]
    // 用一个独立的循环，让逻辑更清晰
    for (int i = 0; i < k; i++) {
        add(nums[i]);   // 将 nums[i] 的贡献加入窗口状态
    }
    update(answer);     // 第一个窗口的答案
 
    // 阶段二：滑动，right 从 k 滑到 n-1
    for (int right = k; right < n; right++) {
        add(nums[right]);           // 新元素进窗（右边界扩展）
        remove(nums[right - k]);    // 旧元素出窗（左边界对应元素是 right-k）
        update(answer);             // 更新答案
    }
    return answer;
}

关键索引关系：当 right = k, k+1, ..., n-1 时，对应的出窗元素是 nums[right - k]，即 nums[0], nums[1], ..., nums[n-k-1]。窗口始终是 [right-k+1, right]。

也可以用显式的 left 指针写，两者等价：

int left = 0;
for (int right = 0; right < n; right++) {
    add(nums[right]);
    if (right - left + 1 == k) {  // 窗口大小达到 k
        update(answer);
        remove(nums[left++]);      // 出窗，left 前进
    }
}

两种写法都要掌握。第一种更紧凑；第二种 left 指针更直观，面试时不容易写出 off-by-one 错误。

---

第 2 章 LeetCode 643：子数组最大平均数

2.1 题目

LeetCode 643 - Maximum Average Subarray I（简单）

给你一个由 $n$ 个元素组成的整数数组 nums 和一个整数 $k$，请你找出平均数最大且长度为 $k$ 的连续子数组，并输出该最大平均数。

任何误差小于 $10^{-5}$ 的答案都将被视为正确答案。

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

输入：nums = [5], k = 1
输出：5.00000

约束：$n\ge k\ge 1$，$-10^4\le nums[i]\le 10^4$。

2.2 暴力思路与优化动机

暴力法枚举所有长度为 $k$ 的子数组，逐个求和再除以 $k$，时间复杂度 $O(nk)$。当 $n=10^5$、$k=5\times 10^4$ 时，约 $5\times 10^9$ 次操作，超时。

优化点：长度为 $k$ 的子数组和等于最大子数组和除以 $k$（平均数与和等价，只需最大化和）。相邻两个子数组的和，差值只有一进一出的两个元素，完全可以增量更新。

2.3 固定窗口解法

public double findMaxAverage(int[] nums, int k) {
    int n = nums.length;
    int sum = 0;
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }
    int maxSum = sum;
 
    // 滑动
    for (int right = k; right < n; right++) {
        sum += nums[right];          // 进窗
        sum -= nums[right - k];      // 出窗
        maxSum = Math.max(maxSum, sum);
    }
 
    return (double) maxSum / k;
}

时间复杂度：$O(n)$（每个元素各被访问一次） 空间复杂度：$O(1)$

2.4 边界细节分析

为什么 maxSum 初始化为 sum（第一个窗口的和）而不是 Integer.MIN_VALUE？

因为在滑动之前，第一个窗口的和就是一个合法答案。如果初始化为 Integer.MIN_VALUE，逻辑上也正确，但多写了一行没必要的代码。以”第一个窗口结果”初始化是更自然的习惯。

题目保证 $n\ge k$，所以第一个窗口一定存在。但如果面试官没有给出这个保证，需要在函数开头加 if (n < k) return 0.0; 这样的防御性代码。

数据类型：数组元素是 int（范围 $[-10^4,10^4]$），$k$ 最大 $10^5$，因此和的范围是 $[-10^9,10^9]$，恰好在 int 的表示范围 $[-2.1\times 10^9,2.1\times 10^9]$ 内，不需要用 long。但如果约束更大（元素范围 $10^9$，$k$ 为 $10^5$），则和可能溢出，需要 long。

生产避坑：求和时的数据类型溢出

面试时遇到求和操作，第一反应是检查数据范围。当单个元素最大值 × 数组长度 > $2.1\times 10^9$ 时，需要用 long 累加。不要依赖测试用例来发现溢出问题——面试官可能没有故意设计溢出的测试用例。

---

第 3 章 LeetCode 1343：大小为 K 且平均值大于等于阈值的子数组数目

3.1 题目

LeetCode 1343 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold（中等）

给你一个整数数组 arr 和两个整数 k 和 threshold，请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5],[5,5,8] 的平均值分别为 4,5,6，均 >= 4。

输入：arr = [1,1,1,1,1], k = 1, threshold = 0
输出：5

3.2 问题分析：计数型固定窗口

与 643 不同，这道题不是求最大值，而是统计满足条件的窗口个数。计数型窗口的框架与求最值的框架相同，只是”更新答案”部分改为”条件判断后计数”。

“平均值 ≥ threshold” 等价于 “窗口和 ≥ threshold * k”（乘以 $k$ 避免浮点运算，消除除法）。

public int numOfSubarrays(int[] arr, int k, int threshold) {
    int n = arr.length;
    int sum = 0;
    int count = 0;
    int minSum = threshold * k;  // 预先计算门限值，避免每次都乘法
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }
    if (sum >= minSum) count++;
 
    // 滑动
    for (int right = k; right < n; right++) {
        sum += arr[right];
        sum -= arr[right - k];
        if (sum >= minSum) count++;
    }
    return count;
}

时间复杂度：$O(n)$ 空间复杂度：$O(1)$

3.3 优化细节：提前计算 threshold * k

threshold * k 的计算可以在循环外提前完成，避免在每次比较时重复计算。这是一个小优化，但体现了”循环不变量提取到循环外”的编程习惯——循环内只保留会改变的值。

数据类型检查：arr[i] 最大 $10^5$，$k$ 最大 $10^5$，所以 sum 最大 $10^{10}$，超过 int 的范围，需要用 long：

// 注意数据类型
long sum = 0;
long minSum = (long) threshold * k;
// ...

核心概念：整数到浮点数的等价转换

当题目涉及”平均值 ≥ X”的判断时，标准操作是将”和 ÷ k ≥ X”两边同乘 k，变为”和 ≥ X × k”。这样避免了浮点除法，既消除精度问题，又加快了运行速度。这个技巧在面试中非常实用。

---

第 4 章 LeetCode 567：字符串的排列

4.1 题目

LeetCode 567 - Permutation in String（中等）

给你两个字符串 s1 和 s2，如果 s2 中包含 s1 的某个排列（即字母异位词），返回 true；否则返回 false。

输入：s1 = "ab", s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列 "ba"。

输入：s1 = "ab", s2 = "eidboaoo"
输出：false

4.2 字母异位词的本质：频率计数等价

“字母异位词”的本质是：两个字符串包含的字母及其数量完全相同，只是顺序不同。判断两个字符串是否互为字母异位词，只需判断它们的字符频率向量是否相同。

所以问题转化为：在 s2 中，是否存在一个长度为 s1.length() 的子串，使其字符频率与 s1 的字符频率完全相同？

这是一个固定窗口 + 字符计数的经典问题。窗口大小固定为 s1.length()，每次移动后检查窗口内的字符频率是否与 s1 匹配。

4.3 解法一：暴力频率比较

每次移动窗口后，重新统计窗口内字符频率并与 s1 比较：

public boolean checkInclusion(String s1, String s2) {
    int k = s1.length();
    int n = s2.length();
    if (k > n) return false;
 
    int[] need = new int[26];
    for (char c : s1.toCharArray()) need[c - 'a']++;
 
    for (int left = 0; left <= n - k; left++) {
        int[] window = new int[26];
        for (int i = left; i < left + k; i++) {
            window[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(window, need)) return true;
    }
    return false;
}
// 时间复杂度：O(k * n)，每次窗口移动都重新统计 k 个字符

这是 $O(kn)$ 的解法，对于大输入会超时。

4.4 解法二：增量更新窗口频率

频率计数同样支持增量更新：进窗时对应字符计数 +1，出窗时对应字符计数 -1。每次只更新两个字符，避免全量重算。

但每次还是需要比较整个频率数组（26 个元素），比较本身是 $O(26)=O(1)$ 的（字母表固定大小），所以整体是 $O(n)$。

public boolean checkInclusion(String s1, String s2) {
    int k = s1.length();
    int n = s2.length();
    if (k > n) return false;
 
    int[] need = new int[26];    // s1 的字符频率
    int[] window = new int[26];  // 当前窗口的字符频率
 
    for (char c : s1.toCharArray()) need[c - 'a']++;
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        window[s2.charAt(i) - 'a']++;
    }
    if (Arrays.equals(window, need)) return true;
 
    // 滑动
    for (int right = k; right < n; right++) {
        window[s2.charAt(right) - 'a']++;       // 进窗
        window[s2.charAt(right - k) - 'a']--;   // 出窗
        if (Arrays.equals(window, need)) return true;
    }
    return false;
}
// 时间复杂度：O(26n) = O(n)；空间复杂度：O(26) = O(1)

4.5 解法三：用”匹配计数器”替代数组比较

解法二每次调用 Arrays.equals 虽然是 $O(26)$，但常数因子仍有优化空间。更优雅的方案是维护一个 match 计数器，记录已满足的字符种类数，当 match == 26（或者更精确地：当所有需要的字符种类都已满足）时，说明匹配成功。

这是字符计数型窗口的经典优化技巧：

public boolean checkInclusion(String s1, String s2) {
    int k = s1.length();
    int n = s2.length();
    if (k > n) return false;
 
    int[] need = new int[26];   // need[c] > 0 表示还需要 c 字符 need[c] 个
    for (char c : s1.toCharArray()) need[c - 'a']++;
 
    // match：need 中值 == 0 的字符种类数（即已满足的种类数）
    // 初始时，need 中为 0 的位置是"s1 中不包含的字符"，初始化 match 为这些字符的数量
    int match = 0;
    for (int count : need) {
        if (count == 0) match++;
    }
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        int c = s2.charAt(i) - 'a';
        need[c]--;
        if (need[c] == 0) match++;   // 某字符恰好满足，match+1
    }
    if (match == 26) return true;
 
    // 滑动
    for (int right = k; right < n; right++) {
        // 右边进窗
        int inChar = s2.charAt(right) - 'a';
        if (need[inChar] == 0) match--;  // 原来恰好满足，现在多了一个，变为不满足
        need[inChar]--;
 
        // 左边出窗
        int outChar = s2.charAt(right - k) - 'a';
        need[outChar]++;
        if (need[outChar] == 0) match++;  // 恢复到恰好满足
 
        if (match == 26) return true;
    }
    return false;
}

这个解法避免了每次调用 Arrays.equals，常数因子更小，但代码稍复杂。

设计哲学：need 数组的语义

need[c] 表示当前窗口还”缺少” c 字符的数量。need[c] > 0 表示窗口内 c 不够，需要更多；need[c] == 0 表示恰好满足；need[c] < 0 表示窗口内 c 过多了。这个设计让进窗（need[c]--）和出窗（need[c]++）的代码非常对称。

这个技巧在第 03 篇”最小覆盖子串”中会得到更充分的应用。

4.6 三种解法的对比

解法	时间复杂度	空间复杂度	说明
暴力枚举	$O(kn)$	$O(k)$	每次重算频率，超时
增量更新 + 数组比较	$O(26n)$	$O(26)$	简单易写，推荐面试时首选
增量更新 + match 计数器	$O(n)$（常数更小）	$O(26)$	最优，但代码稍复杂

面试中，解法二（增量更新 + 数组比较）是最推荐的写法：思路清晰，代码量适中，不容易出 bug。解法三在追求极致性能时使用。

---

第 5 章 固定窗口的变体与注意事项

5.1 字符串 vs 数组：本质相同，细节不同

三道例题中，643 和 1343 是数组，567 是字符串。字符串和数组在固定窗口中的处理几乎相同，区别只在：

• 数组：nums[right]，nums[right - k]，元素可以是任意整数
• 字符串：s.charAt(right)，s.charAt(right - k)，元素是字符（char），通常映射到 int 数组索引

字符串字符的索引：

• 全小写字母：c - 'a'，范围 [0, 25]，用 int[26] 数组
• 全大写字母：c - 'A'，范围 [0, 25]，用 int[26] 数组
• 大小写混合：c - 'A'，范围 [0, 57]（大小写字母间有 6 个非字母字符），或用 HashMap
• 任意字符：用 HashMap<Character, Integer>

5.2 “右进左出”的等价写法

固定窗口的”右进左出”有两种等价写法，都需要掌握：

写法 A（推荐）：right 从 k 开始，出窗元素是 nums[right - k]

// 先初始化第一个窗口
for (int i = 0; i < k; i++) process_in(nums[i]);
check_answer();
// 再滑动
for (int right = k; right < n; right++) {
    process_in(nums[right]);
    process_out(nums[right - k]);
    check_answer();
}

写法 B：right 从 0 开始，窗口满了才处理

int left = 0;
for (int right = 0; right < n; right++) {
    process_in(nums[right]);
    if (right - left + 1 == k) {  // 窗口大小 == k
        check_answer();
        process_out(nums[left++]);
    }
}

写法 B 的循环统一，但 check_answer() 和 process_out() 的位置容易混淆——是先更新答案再出窗，还是先出窗再更新？正确顺序是先更新答案，再出窗（因为要在当前窗口满 k 时记录答案）。

5.3 固定窗口不等于简单窗口

别因为”固定”就认为它简单。当窗口状态维护涉及较复杂的数据结构时，固定窗口同样具有挑战性：

• 维护中位数：需要两个堆（最大堆 + 最小堆）维护窗口的有序性，每次进出操作 $O(\log k)$，适合 LeetCode 480
• 维护众数：需要哈希表记录频率，并追踪最高频率，LeetCode 2780
• 维护 XOR 值：支持增量（XOR 自身可逆），LeetCode 1310 的变种

这些题目的难点不在于窗口框架本身，而在于选对维护状态的数据结构。框架永远是那三步：初始化、进窗、出窗；难点在于每步的具体操作。

---

第 6 章 综合练习与面试心法

6.1 本章三题的共性总结

题目	窗口状态	进窗操作	出窗操作	答案更新
643 最大平均子数组	sum（整数求和）	sum += x	sum -= x	maxSum = max(maxSum, sum)
1343 满足均值阈值的子数组数目	sum（整数求和）	sum += x	sum -= x	if sum >= minSum: count++
567 字符串排列	window[26]（字符频率）	window[c]++	window[c]--	Arrays.equals(window, need)

共性：

1. 窗口状态都支持 $O(1)$ 的增量更新
2. 进窗和出窗操作完全对称（互逆）
3. 答案在每次窗口稳定（大小等于 $k$）后检查

6.2 面试时的答题流程

遇到固定窗口题，面试中按以下步骤阐述思路：

第一步，识别类型：明确说出”这是一道固定窗口题，窗口大小为 $k$”。

第二步，定义状态：说明维护什么状态，以及如何增量更新。

第三步，写代码：按”初始化 → 滑动（进窗 → 出窗 → 更新答案）“的顺序写代码。

第四步，分析复杂度：说明时间 $O(n)$（每个元素进出各一次），空间 $O(1)$ 或 $O(\text{状态大小})$。

第五步，处理边界：检查 k > n 的情况，以及数值溢出的风险。

核心概念：面试评分标准中的"清晰度"

面试官评分时，“能快速识别题目类型并命名”是加分项。直接说”这是固定窗口”，比在纸上画半天才想出思路要好得多。本专栏反复强调模式识别，就是为了培养这种快速定型的能力。

6.3 延伸题目推荐

掌握本篇三题后，可以挑战以下类似题目：

• LeetCode 219 存在重复元素 II：固定窗口 + 哈希表查重
• LeetCode 1052 爱生气的书店老板：固定窗口 + 前缀标记，稍有变体
• LeetCode 2090 半径为 k 的子数组平均值：多组固定窗口的管理
• LeetCode 2461 长度为 K 子数组中的最大和（子数组元素两两不同）：固定窗口 + 去重计数

---

本篇总结

本篇通过三道递进难度的题目，系统讲解了固定长度滑动窗口的核心机制：

1. 增量更新是固定窗口的性能关键——进窗操作和出窗操作必须互逆
2. 数组状态（整数求和、字符频率计数）比极值状态更容易维护，因为它们支持 $O(1)$ 的增量更新
3. 字符频率窗口的核心技巧是用 int[26] 数组替代哈希表，以及用 match 计数器替代整个数组的比较，这两个优化在后续字符串类题目中反复出现

下一篇进入可变窗口的核心——最小覆盖子串（LeetCode 76），将深度解析”收缩条件”和”答案更新时机”这两个可变窗口最关键的设计点。

---

参考与延伸

• 01 滑动窗口算法原理全景：从暴力枚举到 O(n) 的思维跃迁 — 窗口机制的底层原理
• 06 字符计数窗口：哈希表与滑动窗口的黄金组合 — 字符计数的进阶应用
• 07 单调队列优化滑动窗口：O(n) 求窗口极值的艺术 — 解决固定窗口中极值维护的难题

---

课后练习

LeetCode 2090 - 半径为 k 的子数组平均值（中等）

给你一个下标从 0 开始的数组 nums，返回一个长度与 nums 相同的数组 avgs，其中 avgs[i] 是以 i 为中心、半径为 k 的子数组（共 2k+1 个元素）的平均值；若不足则 avgs[i] = -1。

提示：固定窗口大小 2k+1，注意窗口内元素求和可能溢出 int，改用 long；avgs[i] 仅在 i >= k && i < n - k 时有效。