第3类题型：滑动窗口

为什么滑动窗口题你明明刷过，一到面试还是容易收缩错

很多同学第一次见滑动窗口，会觉得它只是“双指针换个名字”。因为代码结构经常也是 left、right 两个变量，再套一层 while，表面上不难。但真正到了面试现场，滑动窗口反而很容易暴露出三类问题：

• 你会背模板，却说不清窗口里到底维护了什么状态。
• 你知道要收缩，却解释不出为什么此时收缩不会漏答案。
• 你能把代码写个大概，但固定窗口和可变窗口经常混着用。

如果你现在正处在“Easy 还能做，Medium 一追问就乱”的阶段，滑动窗口很值得单独拿出来练。读完这篇，你至少要把 3 件事练熟：先判断题目是不是连续区间问题、先定义窗口状态再写模板、能在面试里解释清楚窗口什么时候扩张、什么时候收缩、什么时候更新答案。

---

---

1. 核心知识点

滑动窗口常见在字符串和数组题里，核心是维护一个连续区间 [left, right]，让这个区间始终满足某个条件，或者在扩张和收缩过程中寻找最优答案。

你可以把它理解成双指针的一个特化版本，但它更强调“窗口内部状态”的维护，比如：

• 当前窗口中每个字符出现了几次。
• 当前窗口和是多少。
• 当前窗口是否满足“无重复”“包含所有目标字符”等条件。

最常见的框架是：

int left = 0;
for (int right = 0; right < s.length(); right++) {
    // 把 s[right] 纳入窗口

    while (窗口需要收缩) {
        // 移出 s[left]
        left++;
    }

    // 更新答案
}

难点不在模板，而在两个问题：

• 什么时候扩张。
• 什么时候收缩。

动画辅助理解：先扩张，再在窗口失效时收缩

滑动窗口最适合用 3. 无重复字符的最长子串 建立第一印象。你可以先打开本地动画页：

滑动窗口：无重复字符分步动画

这个动画最值得观察的是 4 步：

• right 先把新字符纳入窗口。
• 一旦发现窗口冲突，比如某个字符重复，先别重开，而是移动 left 修复状态。
• 只有窗口重新合法后，才更新答案。
• 每个元素最多进窗口一次、出窗口一次，所以总复杂度才能压到 O(n)。

拿 s = "abca" 举例，窗口状态变化是这样的：

步骤	当前窗口	发生了什么	为什么这样做
right = 0	"a"	放入 a	当前无冲突，答案可更新为 1
right = 1	"ab"	放入 b	当前无冲突，答案可更新为 2
right = 2	"abc"	放入 c	当前无冲突，答案可更新为 3
right = 3	"abca"	放入第二个 a 后出现重复	这时不能直接更新答案，而要移动 left，直到窗口重新合法
收缩后	"bca"	左边的 a 被移出	窗口恢复无重复，但最长答案仍是 3

2. 这类题在面试里考什么

滑动窗口题主要考两个能力：

• 你能不能把“连续区间”抽象成状态维护问题。
• 你能不能清楚地定义窗口何时有效、何时无效。

面试官往往会追问：

• 你的窗口里存的是什么状态。
• 为什么这个条件满足时要收缩。
• 更新答案是在收缩前还是收缩后。

如果这三个问题答不清楚，代码大概率也写不稳。

---

3. 高频题清单

题目	来源	难度	高频属性
209. 长度最小的子数组	面试经典 150	Medium	基础高频
3. 无重复字符的最长子串	LeetCode 热题 100	Medium	真实面经高频
438. 找到字符串中所有字母异位词	LeetCode 热题 100	Medium	高频 Medium
567. 字符串的排列	面试经典 150	Medium	高频 Medium

4. 这类题最容易犯的 3 个错误

1. 只记住了双层 while 结构，却没定义窗口状态。
2. 不知道什么时候该收缩，导致答案更新时机全乱。
3. 字符串题里频次数组和 HashMap 切换不清，写得又慢又乱。

---

5. 代表题精讲 1

题目

209. 长度最小的子数组

思路

题目要求找到和大于等于 target 的最短连续子数组长度。因为数组元素都是正数，所以窗口和随着右边扩张只会变大，这就给了我们收缩窗口的依据。

做法：

1. 右指针不断向右扩张，把新元素加入窗口和。
2. 当窗口和 >= target 时，说明当前窗口已经满足要求，可以尝试收缩左边，看看能否变得更短。
3. 每次收缩前更新最短长度。

Java 代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int best = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];

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

        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

复杂度

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

边界提醒

这题能直接用可变长度滑动窗口，一个很关键的前提是：数组元素都是正数。因为全是正数时，窗口右扩后，窗口和只会变大；一旦 sum >= target，左边收缩才有明确意义。

如果数组里允许负数，这个单调性就没了。此时你不能直接套这个模板，往往要改用前缀和、单调队列或别的思路。这一点在面试里如果你能主动说出来，专业度会明显更高。

如果这是面试现场，你可以这样说

这题我会用滑动窗口，因为题目找的是连续子数组，而且数组元素都是正数，所以窗口和随右指针扩张单调增加。当窗口和达到目标时，就可以移动左指针尝试收缩，从而找到更短的满足条件的区间。每个元素最多进窗口一次、出窗口一次，所以整体复杂度是 O(n)。

---

6. 代表题精讲 2

题目

438. 找到字符串中所有字母异位词

思路

这题的关键是：窗口长度固定为 p.length()，只要窗口里的字符频次和 p 完全一致，这个窗口就是一个异位词。

因为字符只包含小写字母，所以可以直接用长度为 26 的数组做计数，而不是 HashMap。

一种常用做法是维护一个差分数组：

• 先把 p 的字符频次加进去。
• 扫描窗口时，把进入窗口的字符减掉。
• 当窗口长度超过 p.length() 时，把离开窗口的字符再加回来。
• 每次窗口长度刚好等于 p.length() 时，检查计数数组是否全为 0。

Java 代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }

        int[] count = new int[26];
        for (char c : p.toCharArray()) {
            count[c - 'a']++;
        }

        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'a']--;

            if (right - left + 1 > p.length()) {
                count[s.charAt(left) - 'a']++;
                left++;
            }

            if (right - left + 1 == p.length() && allZero(count)) {
                result.add(left);
            }
        }

        return result;
    }

    private boolean allZero(int[] count) {
        for (int value : count) {
            if (value != 0) {
                return false;
            }
        }
        return true;
    }
}

复杂度

• 时间复杂度：O(26 * n)，也可以视为 O(n)
• 空间复杂度：O(1)

边界提醒

这里用 int[26] 的前提是题目明确说了字符串只包含小写字母。如果字符集扩大到大小写字母、Unicode 或任意字符流，就要根据题目条件改成 HashMap<Character, Integer> 或更大的计数结构，而不是死背 26。

如果这是面试现场，你可以这样说

这题我会把它看成固定长度窗口。窗口长度始终等于 p.length()，只要窗口中的字符频次和 p 一样，就说明这个窗口是一个异位词。因为只涉及 26 个小写字母，所以我会优先用计数数组维护频次，而不是 HashMap。这样写法更直接，常数也更小。

---

7. 其余题模板与关键片段

3. 无重复字符的最长子串

核心是窗口中不能出现重复字符：

int[] count = new int[128];
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
    count[s.charAt(right)]++;
    while (count[s.charAt(right)] > 1) {
        count[s.charAt(left)]--;
        left++;
    }
    best = Math.max(best, right - left + 1);
}

567. 字符串的排列

和异位词问题本质接近，只是问是否存在，因此你可以把它当成“找到一个满足条件的固定长度窗口就立刻返回 true”：

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }

        int[] count = new int[26];
        for (char c : s1.toCharArray()) {
            count[c - 'a']++;
        }

        int left = 0;
        for (int right = 0; right < s2.length(); right++) {
            count[s2.charAt(right) - 'a']--;

            if (right - left + 1 > s1.length()) {
                count[s2.charAt(left) - 'a']++;
                left++;
            }

            if (right - left + 1 == s1.length() && allZero(count)) {
                return true;
            }
        }

        return false;
    }

    private boolean allZero(int[] count) {
        for (int value : count) {
            if (value != 0) {
                return false;
            }
        }
        return true;
    }
}

这类固定窗口题有一个很实用的面试表达：窗口长度由题目直接给定，所以你的关注点不是“何时收缩到合法”，而是“每次窗口长度超过目标值时，把最左边那个元素移出去，让窗口长度重新回到固定值”。

8. 什么时候用固定长度窗口，什么时候用可变长度窗口

你可以用一个很快的判断法：

• 题目要求“长度恰好为 k 的子串 / 子数组”，优先想固定长度窗口。
• 题目要求“满足某条件的最长 / 最短连续区间”，优先想可变长度窗口。

常见对应关系是：

题型信号	更适合的窗口模型	典型题
长度固定、比较频次、判断是否存在	固定长度窗口	438、567
求最短满足条件区间	可变长度窗口	209
求最长合法区间	可变长度窗口	3

真正写代码前，你最好先用一句话把窗口状态说出来：

• 我维护的是窗口内字符频次。
• 我维护的是窗口和。
• 我维护的是当前窗口是否还合法。

---

9. 错题本记录方式

滑动窗口题建议记录：

• 我维护的窗口状态是什么。
• 窗口何时有效、何时无效。
• 我为什么要在这个时机收缩。
• 这题是可变长度窗口还是固定长度窗口。

10. 面试前 3 分钟速记

• 连续子串 / 子数组，优先想滑动窗口。
• 先定义窗口里维护什么状态，再写模板。
• 正数数组的最短 / 最长区间题，常见可变长度窗口。
• 异位词、排列问题，常见固定长度窗口。
• 小写字母优先用 int[26]，别一上来就上 HashMap。

11. 最后总结：滑动窗口不是背模板，而是先定义状态

如果你只能记住一句话，那就是：滑动窗口题真正的核心不是 while 模板，而是“窗口里维护什么状态，窗口在什么条件下算合法”。

面试时你只要能按这个顺序去讲，思路就不容易乱：

1. 先判断这是不是连续区间问题。
2. 再判断这是固定长度窗口还是可变长度窗口。
3. 明确窗口里维护的是频次、和，还是合法性条件。
4. 最后再决定答案是在扩张后更新，还是在收缩到合法后更新。

这样你不只是会写一道题，而是真的开始掌握滑动窗口这一类题的共性。

---

上一篇：【Java实习面试算法冲刺】双指针
下一篇：正在路上……

感谢阅读，记得点赞、关注、收藏，欢迎各位评论区交流！！！