LeetCode Hot 100 · 滑动窗口篇

滑动窗口是字符串类高频考点的核心套路。它的本质是维护一个左右边界可动态调整的区间，右指针负责「扩张」引入新元素，左指针负责「收缩」剔除非法元素，全程让窗口保持某种合法性，并在合法时统计答案。

本分类只有两道题，却恰好覆盖了滑动窗口的两大经典形态：

• 可变长窗口（#3 无重复字符的最长子串）：窗口长度不固定，追求「最长」。
• 固定长窗口（#438 找到字符串中所有字母异位词）：窗口长度锁定为 p.length()，追求「恰好匹配」。

两题掌握之后，LeetCode 上绝大多数滑动窗口题（76、567、424、1004 等）都能套同一个模板秒掉。

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

题意

给定字符串 s，找出其中不含重复字符的最长子串的长度。

输入：s = "abcabcbb"
输出：3（"abc"）

题目本质

本质是一个可变长滑动窗口问题：维护一个无重复字符的窗口，右指针扩张，一旦发现重复就收缩左边，全程记录最大窗口长度。

现实类比

不重复点菜：从菜单起点开始依次点菜（右移指针），一旦发现点了重复的菜，就从最开始逐个取消（左移指针），直到重复消失。全程记录「最多能同时点多少道不同的菜」。

难点与易错点

1. 「重复」的判断时机与收缩方向：不是发现重复后整体清空重来，而是只收缩左边界到「重复消除」为止。有人写成 left = 重复字符位置 + 1 一步到位（用 HashMap 存字符下标），也有人写成「逐个 left++ 直到计数回落」——两种都对，但不能混用。存下标的写法要求 map 里存的是「最新位置」，一旦用旧位置回退 left 就会算错。

2. 窗口长度的计算口径：代码里常让 right 先右移再入窗口（即窗口是左闭右开 [left, right)），此时长度是 right - left，不要再 +1；如果写成闭区间 [left, right]，长度才是 right - left + 1。这两种口径混用是手撕时最容易翻车的地方。

3. 边界条件：空串 s = "" 应返回 0；全相同字符 "bbbb" 应返回 1。若 maxLen 初始化为 0、循环内正常更新，这两种都能自然覆盖，但若在循环外漏了初始判断或把 maxLen 初始化成 Integer.MIN_VALUE 就会出错。

4. map 的更新顺序：先 window.merge(entering, 1, ...) 再判断 > 1。若先判断再加入，首次入窗口的字符会被误判为重复。

解法一：暴力 / 直观

枚举所有起点，从每个起点向后扩展，用 HashSet 判重，一旦重复就停止这一轮，取所有轮次的最大长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLen = 0;
        // 枚举每个位置作为窗口起点
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            // 从 i 出发向后扩展，直到遇到重复字符
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (seen.contains(c)) {
                    break; // 出现重复，本轮窗口到此为止
                }
                seen.add(c);
                maxLen = Math.max(maxLen, j - i + 1); // 闭区间 [i, j] 长度 = j - i + 1
            }
        }
        return maxLen;
    }
}

复杂度推导：

• 外层 i 枚举 n 个起点，内层 j 最多走 n 步，两层循环的上界是 n * n 次；每次 HashSet 操作 O(1)。
• 时间复杂度：O(n²)。
• 空间复杂度：每个起点一个 HashSet，存当前子串的字符，O(min(n, 字符集大小))。

瓶颈：相邻两轮窗口之间大量重叠（如 "abcd..." 中，起点 0 和起点 1 的窗口共享 "bcd" 这段），暴力法把这段重复判重了一遍又一遍，没有复用上一轮已经验证过的信息。

解法二：优化 / 最优（滑动窗口 + HashMap 计数）

不重置窗口，让 right 一路向右扩张，遇到重复时只把 left 向右收缩到「重复消除」为止。每个字符最多进窗口、出窗口各一次。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 记录窗口 [left, right) 内每个字符的出现次数
        Map<Character, Integer> window = new HashMap<>();
        int left = 0;
        int right = 0;
        int maxLen = 0;
        char[] chars = s.toCharArray();

        while (right < s.length()) {
            char entering = chars[right];
            // Java 8 merge：key 不存在时放 1，存在时 +1
            window.merge(entering, 1, Integer::sum);
            right++; // 窗口为左闭右开 [left, right)

            // 窗口内出现重复字符，收缩左边界直到重复消除
            while (window.get(entering) > 1) {
                char leaving = chars[left];
                // 将左边字符计数 -1，减到 0 时该字符已离开窗口
                window.merge(leaving, -1, Integer::sum);
                left++;
            }

            // 此时窗口内无重复，更新最大长度
            // right - left 即为当前窗口大小（right 已右移，无需 +1）
            maxLen = Math.max(maxLen, right - left);
        }

        return maxLen;
    }
}

> **💭 思考**：为什么「无重复字符最长子串」要把暴力改成「右进左出」的滑动窗口？一步步想——暴力枚举每个起点，瓶颈是相邻两轮窗口大量重叠，`"bcd"` 这段被重复判重了一遍又一遍。想复用，就让 `right` 一路向右、永不回退，只有出现重复时才把 `left` 向右收缩到「重复消除」——这样每个字符最多进窗口、出窗口各一次，O(n) 就够。窗口类型由「求最长、无重复」决定是可变长的：右指针扩张引入新元素，不合法就收缩左边界，合法时记录 `max(right-left)`。

复杂度逐步推导（禁止只报 O(n)，一步步来）：

• right 指针的移动次数：外层 while 每执行一轮 right++ 一次，right 从 0 单调递增到 n，恰好移动 n 次。
• left 指针的移动次数：left 只在「内层 while 满足时」才 left++，且 left 全程单调不减、永不回退，其值最终不超过 n，所以 left++ 总共最多执行 n 次。
• 单次操作代价：right 和 left 每移动一次，只做常数次的 HashMap merge / get，均为 O(1)。
• 综合：总代价 = (right 移动 n 次 + left 移动至多 n 次) × O(1) = O(n + n) = O(n)。
• 空间复杂度：window 最多同时存「当前窗口内不同字符」的个数，受字符集大小约束，为 O(min(n, 字符集大小))（ASCII 为 128，Unicode 更大）。

多解法对比

在本题约束下，字符串长度可达 5×10⁴，暴力 O(n²) 在最坏情况下会超时；而滑动窗口把「每个字符进出窗口各一次」摊成 O(n)，是唯一能通过且代码简洁的解法，因此选它作为最优解。

CodeTop 变体

• 字节高频追问：若题目保证 s 只含 26 个小写字母，能否把 HashMap 换成 int[26]（或 int[128]）数组？为什么更好？——数组避免了 Character 装箱和哈希寻址，常数更小，是字节手撕常考的微优化。
• 腾讯 / 阿里追问：返回最长子串本身而不是长度。——滑动时同时记录 maxLen 对应的 start 下标，结束时 s.substring(start, start + maxLen)。
• 同套路延伸题：
  • 159. 至多包含两个不同字符的最长子串（可变长窗口，约束由「无重复」变为「至多 k 种」）。
  • 340. 至多包含 k 个不同字符的最长子串（159 的泛化，会员题，字节/阿里考过）。
  • 424. 替换后的最长重复字符（窗口内维护最大频次，配合「窗口长度 - 最大频次 ≤ k」判定）。
  • 1004. 最大连续 1 的个数 III / 2024. 考试的最大困扰度（「至多翻转 k 次」的同类收缩判定）。

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

题意

给定字符串 s 和 p，找到 s 中所有 p 的异位词（字母构成完全相同、顺序任意）的起始索引。

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]

题目本质

本质是一个固定长度滑动窗口问题：维护一个长度等于 p.length() 的窗口，通过比较窗口内字符频次和 p 的字符频次来判断异位词。

现实类比

寻找食材组合：冰箱（p）里有 a、b、c 各一份，在超市货架（s）上滑动一个固定大小的购物框，每次框内食材种类和数量与冰箱完全一样时，记录当前框的起点位置。

难点与易错点

1. 固定长度 ≠ 只需要看窗口长度：判断异位词的充分条件是「窗口大小等于 p.length()」且「窗口内每种字符频次不超过 need」。少了「不超过 need」这个约束，"abx" 这种同长度但字符不对的窗口会被误判。反过来，若用「每种字符频次恰好相等」逐一比对，则需要 O(字符集) 的额外扫描，不如收缩法优雅。

2. 收缩条件的边界：内层 while 的条件是 window[entering] > need[entering]，即只对刚进窗口的那个字符做超量检查。很多人写成「遍历所有字符检查」，不仅多此一举，还容易在 need 中不存在的字符上写错 getOrDefault。

3. getOrDefault 与 map 更新顺序：need 里不存在的字符（如样例中的 e、b 之外的字符）其 need 值为 0，进入窗口后必然 window > need，会立刻被收缩弹出——这是「跳过无关字符」的关键，务必用 getOrDefault 而不是直接 get，否则对不存在的 key 取 null 会抛 NPE。

4. 结果判定的位置：if (right - left == p.length()) 必须放在收缩完成后。若放在收缩前，可能把「超量字符尚未弹出」的非法窗口也算进去。

解法一：暴力 / 直观

枚举 s 中每个长度为 p.length() 的起点，取出子串与 p 分别排序后比较，相等即命中。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int m = p.length();
        char[] target = p.toCharArray();
        Arrays.sort(target); // 将 p 排序作为比较基准

        // 枚举每个可能的窗口起点
        for (int i = 0; i + m <= s.length(); i++) {
            char[] sub = s.substring(i, i + m).toCharArray();
            Arrays.sort(sub); // 子串排序
            if (Arrays.equals(sub, target)) {
                result.add(i);
            }
        }
        return result;
    }
}

复杂度推导：

• 起点共 n - m + 1 个（约 O(n) 个），每个窗口取子串 O(m) + 排序 O(m log m) + 比较 O(m)。
• 时间复杂度：O(n · m log m)。
• 空间复杂度：每次排序用 O(m) 辅助空间。

瓶颈：相邻两个窗口共享 m - 1 个字符，暴力法每次都重新排序整段窗口，把共享部分的比较工作重复了约 m 倍。当 m 接近 n 时接近 O(n² log n)，必然超时。

解法二：优化 / 最优（固定窗口 + 双 HashMap 频次）

用两个 HashMap 分别记录 p 的期望频次 need 与当前窗口的实际频次 window，窗口右进左出、维持「每种字符不超过需求量」，当窗口长度恰好等于 p.length() 时即为异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // need: p 中每种字符的期望频次
        Map<Character, Integer> need = new HashMap<>();
        // window: 当前滑动窗口内每种字符的实际频次
        Map<Character, Integer> window = new HashMap<>();

        // 构建需求表
        for (char c : p.toCharArray()) {
            need.merge(c, 1, Integer::sum);
        }

        List<Integer> result = new ArrayList<>();
        char[] chars = s.toCharArray();
        int left = 0;
        int right = 0;

        while (right < s.length()) {
            char entering = chars[right++];
            window.merge(entering, 1, Integer::sum);

            // 若 entering 在 window 中的频次超过 need 中的频次，收缩左边
            // 保证窗口是 p 的子多集（每种字符不超过需求量）
            while (window.getOrDefault(entering, 0) > need.getOrDefault(entering, 0)) {
                char leaving = chars[left++];
                window.merge(leaving, -1, Integer::sum);
            }

            // 窗口大小恰好等于 p 的长度 → 此时窗口是 p 的异位词
            if (right - left == p.length()) {
                result.add(left);
            }
        }

        return result;
    }
}

> **💭 思考**：为什么异位词题用「固定窗口」而不是「可变窗口」？一步步想——异位词要求窗口长度**恰好**等于 `p.length()`，这是硬约束，所以窗口类型天然是固定长。暴力的瓶颈是每个窗口都重新排序、重复比较 `m-1` 个共享字符；改成频次计数后，只需维护 `window` 里每种字符不超过 `need`。关键在收缩条件：只有「刚进窗口的那个字符」改变了频次、可能破坏合法性，其余字符上一轮已保证合法，所以内层 while 只检查这一个字符是否超量——既维持不变量，又避免遍历全部字符的冗余。

复杂度逐步推导（禁止只报 O(n)，一步步来）：

• right 指针：外层 while 每轮 right++ 一次，right 从 0 单调增至 n，恰好移动 n 次。
• left 指针：仅在「某字符超量」时 left++，left 单调不减、总移动次数不超过 n，至多 n 次。
• 单次操作代价：每次移动只做常数次 HashMap merge / getOrDefault，O(1)。
• 综合：总代价 = (n 次 right + 至多 n 次 left) × O(1) = O(n + n) = O(n)。
• 空间复杂度：need 存 p 的字符种类，window 存窗口内字符种类；当题目限定小写字母时两者最多 26 个 key，是常数级 O(1)（若字符集不限，则为 O(字符集大小)）。

进阶优化（面试可口头补充）：由于字符集只有 26 个小写字母，可把两个 HashMap 换成两个 int[26]，用下标 c - 'a' 定位，进一步消除装箱与哈希开销，常数更优；这也是字节手撕常被追问的点。

多解法对比

在本题约束下（s 长度可达 3×10⁴，p 长度可达 n 量级），暴力排序法在最坏情况接近 O(n² log n) 会超时；滑动窗口把「每字符进出窗口各一次」摊成 O(n)，是唯一稳妥的最优解。

CodeTop 变体

• 字节高频（几乎必考）：567. 字符串的排列——判断 s 是否包含 p 的某个排列（即是否存在一个异位词子串）。思路与本题完全同套：固定窗口 + 频次比对，只是返回值从「所有起点」变成「是否存在」，把 result.add 换成直接 return true 即可。
• 腾讯 / 美团追问：76. 最小覆盖子串——从「固定长度异位词」升级为「可变长度最小覆盖」，窗口右扩直到满足 need、再左缩求最小，是滑动窗口模板的终极大题。
• 阿里追问：30. 串联所有单词的子串——把「字符粒度」的异位词升级为「单词粒度」，固定总长度 + 单词频次计数，思路同源。
• 同套路延伸题：固定窗口 + 频次/平均数/方差类统计（如 643. 子数组最大平均数、1343. 大小为 k 且平均值大于等于阈值的子数组数目），都是「固定长窗口 + 增量维护统计量」的同一套模板。

总结：两题的模板心法

一句话记牢：右指针扩张引入新元素 → 不合法就收缩左边界 → 合法时记录答案。这个「右进左出、边收缩边统计」的三步模板，能通吃绝大多数滑动窗口题。

章末提问

1. #3 里 right 和 left 两个指针都有 while 循环，为什么总复杂度不是 O(n²)？——结论：因为两个指针都单调右移、互不回头，right 恰好走 n 步、left 至多走 n 步，合计 O(n+n)=O(n)。内层 while 只是把 left 的 n 步「拆散」到了各轮，总量不变。
2. #438 的收缩条件为什么只检查「刚进窗口的那个字符」是否超量，而不是遍历全部字符？——结论：因为只有新字符改变了频次、可能破坏「不超过 need」的合法性，其余字符上一轮已保证合法。检查这一个字符就能维持不变量，遍历全部是多余且易错的。
3. 判断异位词为什么不能只靠「窗口长度 == p.length()」？——结论：因为长度相等只是必要条件，"abx" 与 "abc" 等长但字符不同，光看长度会误判。必须同时满足「长度相等」和「每种字符频次不超过 need」，后者由收缩循环持续保证。