Java 滑动窗口入门到精通：「子数组最大平均数 I」的基础应用

引言

滑动窗口是解决数组/字符串子区间问题的核心技术，能在$O(n)$时间内高效处理连续区间问题。本文以经典题目「子数组最大平均数 I」为载体，系统讲解滑动窗口的实现原理与应用技巧，助你掌握这一算法思想。

问题定义

给定整数数组 nums 和长度 $k$，求所有长度为 $k$ 的连续子数组中的最大平均数（保留精度）。
示例：
输入：nums = [1,12,-5,-6,50,3], $k=4$
输出：$12.75$（子数组 [12,-5,-6,50] 的平均值）

核心思想

暴力解法缺陷：
遍历所有$n-k+1$个子数组，时间复杂度$O(nk)$，当$n$较大时效率低下。

滑动窗口优化：

1. 窗口初始化：计算首个窗口和$sum$
   $$sum = \sum_{i=0}^{k-1} nums[i]$$

2. 窗口滑动：
   $$sum_{new} = sum_{old} - nums[left] + nums[right]$$
   窗口右移时，移除左边界元素，添加右边界新元素

3. 动态更新：实时比较窗口和的最大值

算法实现（Java）

public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }
    int maxSum = sum;
    
    // 滑动窗口
    for (int i = k; i < nums.length; i++) {
        sum = sum - nums[i - k] + nums[i]; // 窗口右移
        maxSum = Math.max(maxSum, sum);    // 更新最大值
    }
    
    return (double) maxSum / k; // 转换为平均数
}

关键点解析：

1. 边界处理：当$k=1$时，窗口退化为单元素遍历
2. 精度控制：最后一步进行类型转换，避免计算过程丢失精度
3. 空间优化：仅用$O(1)$额外空间，优于前缀和数组的$O(n)$

复杂度分析

• 时间复杂度：$O(n)$
  仅需遍历数组一次（初始化$k$次 + 滑动$n-k$次）
• 空间复杂度：$O(1)$
  仅使用常数级变量

实战技巧

1. 窗口大小固定：适用于子数组长度严格为$k$的问题
2. 边界扩展：可改造为窗口大小可变的问题（如最小覆盖子串）
3. 负数处理：本题含负数元素，但窗口和性质不受影响
4. 早期终止：当$k=n$时直接返回全局平均值

扩展训练

掌握基础后，可挑战进阶题型：

1. 长度不小于$k$的最大平均数子数组（LC 644）
2. 和至少为$k$的最短子数组（LC 862）
3. 包含所有字符的最短子串（LC 76）

结语

滑动窗口通过维护动态区间，将嵌套循环优化为单次遍历，是处理连续子区间问题的利器。理解「子数组最大平均数」的实现逻辑后，可举一反三解决90%的滑动窗口变体问题。