一篇文章让你熟悉滑动窗口

滑动窗口是处理数组 / 字符串子问题的高效算法思想，核心是用一个 “可移动的窗口”（连续的子区间）覆盖数据，通过 “滑动” 窗口（扩大 / 缩小边界）代替暴力枚举，将时间复杂度从 O (n²) 降到 O (n)。

一、先搞懂：什么是滑动窗口？

1. 通俗理解：“移动的望远镜”

想象你用一个固定长度的望远镜观察一排树木（数组）：

• 窗口：望远镜的视野范围（对应数组的连续子区间）；
• 滑动：望远镜向右移动时，左边的树木移出视野，右边的树木进入视野（窗口边界移动，不重复扫描已观察的树木）；
• 核心：通过 “滑动” 避免重复计算，提高效率。

2. 生活例子：超市结账排队

假设超市要求 “每次最多 3 人同时结账”（窗口长度固定为 3）：

• 初始窗口：第 1、2、3 人（处理这 3 人的结账）；
• 滑动窗口：第 3 人结完账后，窗口向右移，变成第 2、3、4 人（不用重新处理第 2、3 人，只新增第 4 人）；
• 优势：不用每次都从第 1 人开始重新统计，节省时间。

3. 核心分类（两种）

二、核心原理：为什么滑动窗口高效？

暴力枚举会重复扫描大量元素（比如找子数组最大和，暴力枚举所有子数组，时间 O (n²)），而滑动窗口的核心是 “只处理新增和移出的元素”：

• 固定窗口：滑动时，左边移出 1 个元素，右边新增 1 个元素，只需计算 “总和 = 原总和 – 移出元素 + 新增元素”（O (1) 操作）；
• 可变窗口：通过扩大右边界加入元素，不满足条件时缩小左边界，全程每个元素只进窗口 1 次、出窗口 1 次（总时间 O (n)）。

就像用望远镜观察树木，移动时不用重新看所有树，只看新进入视野的树和离开视野的树，效率自然高。

三、典型问题拆解（代码实现）

1. 固定窗口：长度为 k 的子数组最大和（LeetCode 643）

问题描述：

给定数组 nums = [1,12,-5,-6,50,3]，k=4，求长度为 4 的子数组的最大和（答案：12 + (-5) + (-6) + 50 = 51）。

滑动窗口思路：

• 初始窗口：前 4 个元素（1,12,-5,-6），总和 = 2；
• 滑动窗口：每次向右移 1 位，总和 = 原总和 – 左边移出元素 + 右边新增元素；
  • 第 1 次滑动：移出 1，新增 50 → 总和 = 2-1+50=51；
  • 第 2 次滑动：移出 12，新增 3 → 总和 = 51-12+3=42；
• 记录过程中最大的总和（51）。

代码实现（Java）：

public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
int windowSum = 0;
// 初始化窗口（前k个元素求和）
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
int maxSum = windowSum;
// 滑动窗口（从k开始，每次右移1位）
for (int i = k; i < n; i++) {
windowSum = windowSum – nums[i – k] + nums[i]; // 移出左元素，加入右元素
maxSum = Math.max(maxSum, windowSum);
}
return (double) maxSum / k;
}

2. 可变窗口：无重复字符的最长子串（LeetCode 3）

问题描述：

给定字符串 s = "abcabcbb"，求无重复字符的最长子串长度（答案：3，对应 "abc"）。

滑动窗口思路：

• 窗口边界：左指针left、右指针right（初始都为 0），窗口为[left, right]；
• 扩大窗口：right向右移，加入当前字符，用哈希表记录字符是否存在；
• 缩小窗口：如果当前字符已在窗口中，left向右移，直到窗口中无重复字符；
• 记录过程中窗口的最大长度。

代码实现（Java）：

public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果字符已存在，且位置在当前窗口内，移动left到重复字符的下一位
if (map.containsKey(c) && map.get(c) >= left) {
left = map.get(c) + 1;
}
map.put(c, right); // 更新字符的最新位置
maxLen = Math.max(maxLen, right – left + 1); // 计算窗口长度
}
return maxLen;
}

四、核心总结（一句话记牢）

• 滑动窗口的本质：用连续的窗口覆盖子问题，通过滑动避免重复计算；
• 固定窗口：先初始化，再滑动（只更新边界元素）；
• 可变窗口：右扩找可行解，左缩优化解（全程 O (n) 效率）。