滑动窗口进阶：无重复字符与字符频次匹配
摘要
当滑动窗口的维护状态从简单的”和”升级为”字符频次哈希表”时，代码复杂度显著提升，但核心的扩张-收缩状态机不变。本文从 Longest Substring Without Repeating Characters 出发，深入讲解哈希表在窗口中的维护技巧，然后分析 Permutation in String 的”窗口内字符恰好匹配”判断，并抽象出”至多 K 个不同字符”这一通用框架，覆盖一类高频面试变体题。
第 1 章 LeetCode 3：无重复字符的最长子串
1.1 题目
LeetCode 3 - Longest Substring Without Repeating Characters（中等）
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
1.2 问题本质：维护”无重复”的窗口
这是一道典型的”最长满足条件的子数组/子串”问题：
- 条件：窗口内没有重复字符
- 目标：找满足条件的最长子串
根据上一篇的框架：right 扩张，当窗口不满足条件时，收缩 left 直到恢复满足，然后在外层更新答案（以 right 为右端的最长满足窗口）。
窗口状态如何维护？
需要知道”窗口内是否有重复字符”。用哈希表 Map<Character, Integer> 记录窗口内每个字符的出现次数，当某个字符的次数 > 1 时，说明有重复。
1.3 解法一：哈希表维护频次
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int maxLen = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 1. 加入窗口：更新字符频次
window.put(c, window.getOrDefault(c, 0) + 1);
// 2. 收缩：当窗口内有重复字符时（c 出现了 2 次），收缩左端
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
window.put(d, window.get(d) - 1);
}
// 3. 更新答案：以 right-1 为右端的最长无重复子串
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}一个优化：收缩时只需检查新加入的字符 c 是否重复（window.get(c) > 1），不需要遍历整个窗口。这是因为每次扩张只加入一个字符，如果有重复，一定是刚加入的字符导致的。
时间复杂度：，right 和 left 各最多移动 步，哈希表操作 。
空间复杂度：， 是字符集大小（如 ASCII 字符集 128）。
1.4 解法二：哈希表记录最近出现下标（更简洁）
另一种思路：Map<Character, Integer> 记录每个字符最近一次出现的下标（而不是频次）。当 right 指向字符 c 时，如果 c 已在窗口内（map.getOrDefault(c, -1) >= left），则直接将 left 跳转到 map.get(c) + 1（跳过重复的那个字符）。
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastIndex = new HashMap<>(); // 字符 -> 最近出现的下标
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 如果 c 在当前窗口内（上次出现位置 >= left），则跳过重复字符
if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
left = lastIndex.get(c) + 1;
}
lastIndex.put(c, right); // 更新 c 的最近出现下标
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}这种写法更简洁，left 直接跳跃而不是一步一步收缩，逻辑更清晰。
1.5 两种写法的对比
| 写法 | 维护的状态 | 收缩方式 | 优缺点 |
|---|---|---|---|
| 频次哈希表 | char -> count（频次） | 一步一步收缩（while 循环） | 通用性强，可推广到”至多 K 个不同字符” |
| 最近下标哈希表 | char -> lastIndex（下标） | 直接跳跃（一步到位） | 代码更简洁，但只适用于”无重复字符”这一特定条件 |
对于”无重复字符”这道题，解法二更简洁。对于需要推广到”至多 K 个不同字符”等变体的题，解法一（频次哈希表）的扩展性更好。
第 2 章 LeetCode 567：字符串的排列
2.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
2.2 核心观察：排列等价于字符频次相同
s1 的某个排列是 s2 的子串，等价于：s2 中存在一个长度为 len(s1) 的子串，其中每个字符的出现次数与 s1 完全相同。
因此，这是一道定长滑动窗口问题（窗口大小固定为 len(s1)），检查每个长度为 len(s1) 的子串的字符频次是否与 s1 的字符频次匹配。
2.3 解法：滑动窗口 + 字符频次数组
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
// 统计 s1 的字符频次
int[] need = new int[26];
for (char c : s1.toCharArray()) need[c - 'a']++;
// 统计初始窗口（前 len(s1) 个字符）的字符频次
int[] window = new int[26];
int k = s1.length();
for (int i = 0; i < k; i++) window[s2.charAt(i) - 'a']++;
// 检查初始窗口
if (Arrays.equals(need, window)) return true;
// 滑动窗口
for (int right = k; right < s2.length(); right++) {
window[s2.charAt(right) - 'a']++; // 加入右端
window[s2.charAt(right - k) - 'a']--; // 移除左端
if (Arrays.equals(need, window)) return true;
}
return false;
}时间复杂度：。Arrays.equals(need, window) 比较 26 个元素，（常数字符集），总时间 。
但每次 Arrays.equals 比较 26 个元素，常数因子较大。有没有更优的方法？
2.4 优化：用 valid 计数器代替全量比较
维护一个整数 valid，表示”当前窗口中满足频次匹配的字符种类数”。当 valid == need 中非零字符的种类数时，说明窗口与 s1 字符频次完全匹配。
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] need = new int[26]; // s1 中每个字符的需求量
int[] window = new int[26]; // 当前窗口中每个字符的数量
int needCount = 0; // s1 中不同字符的种类数
int valid = 0; // 窗口中已满足频次匹配的字符种类数
for (char c : s1.toCharArray()) {
if (need[c - 'a'] == 0) needCount++; // 新的字符种类
need[c - 'a']++;
}
int k = s1.length();
// 初始化第一个窗口
for (int i = 0; i < k; i++) {
char c = s2.charAt(i);
window[c - 'a']++;
if (window[c - 'a'] == need[c - 'a']) valid++; // 该字符频次刚好满足
}
if (valid == needCount) return true;
// 滑动窗口
for (int right = k; right < s2.length(); right++) {
// 加入右端
char in = s2.charAt(right);
window[in - 'a']++;
if (window[in - 'a'] == need[in - 'a']) valid++;
// 移除左端
char out = s2.charAt(right - k);
if (window[out - 'a'] == need[out - 'a']) valid--; // 即将变得不满足
window[out - 'a']--;
if (valid == needCount) return true;
}
return false;
}时间复杂度：（每次移动只更新 2 个字符的状态，）。 空间复杂度：，。
2.5 valid 计数器的维护逻辑
valid 维护”当前窗口中，频次恰好满足 need 的字符种类数”：
- 加入字符
in：window[in]++，若增加后window[in] == need[in]，说明in刚好满足，valid++ - 移除字符
out：若移除前window[out] == need[out]（即将从满足变为不满足），valid--，然后window[out]--
注意顺序：移除时先检查是否满足（再减），加入时先加（再检查是否满足）。
第 3 章 “至多 K 个不同字符”框架
3.1 LeetCode 340：至多包含 K 个不同字符的最长子串
LeetCode 340 - Longest Substring with At Most K Distinct Characters（中等，付费题）
给定一个字符串 s 和一个整数 k，找出至多包含 k 个不同字符的最长子串，返回该子串的长度。
输入：s = "eceba", k = 2
输出：3
解释：满足题意的子串为 "ece"，长度为 3。
输入：s = "aa", k = 1
输出：2
3.2 解法：哈希表 + 可变窗口
public int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> window = new HashMap<>(); // 字符 -> 出现次数
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
// 当窗口内不同字符数超过 k 时，收缩左端
while (window.size() > k) {
char d = s.charAt(left);
left++;
window.put(d, window.get(d) - 1);
if (window.get(d) == 0) window.remove(d); // 频次为 0，从哈希表中删除
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}关键：window.size() 表示窗口内不同字符的种类数（哈希表中 key 的数量）。当 size > k 时收缩，直到 size <= k。
3.3 “恰好 K 个不同字符”的转化技巧
LeetCode 992（Subarrays with K Different Integers）要求”恰好包含 K 个不同整数的子数组数目”。这类”恰好 K 个”问题，可以通过两次”至多”的调用解决：
// 恰好 K 个不同整数的子数组数目
public int subarraysWithKDistinct(int[] nums, int k) {
return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}
// 至多 K 个不同整数的子数组数目（滑动窗口）
private int atMostKDistinct(int[] nums, int k) {
Map<Integer, Integer> window = new HashMap<>();
int left = 0, count = 0;
for (int right = 0; right < nums.length; right++) {
window.put(nums[right], window.getOrDefault(nums[right], 0) + 1);
while (window.size() > k) {
window.put(nums[left], window.get(nums[left]) - 1);
if (window.get(nums[left]) == 0) window.remove(nums[left]);
left++;
}
// 以 right 为右端点的满足条件的子数组数目 = right - left + 1
count += right - left + 1;
}
return count;
}为什么 right - left + 1 是以 right 为右端的合法子数组数目？
当 right 固定，窗口为 [left, right]，所有以 right 为右端、left'（）为左端的子数组都满足”至多 K 个不同整数”。共 right - left + 1 个。
第 4 章 字符频次类滑动窗口的通用框架
4.1 三道题的抽象框架
Longest Substring Without Repeating Characters、Permutation in String、Longest Substring with At Most K Distinct Characters 这三道题，本质上都是：
“维护窗口内的字符频次统计量，当统计量不满足/满足某条件时收缩，找最长/最短满足条件的子串”
| 题目 | 窗口满足条件 | 收缩时机 | 答案更新位置 |
|---|---|---|---|
| 无重复字符最长子串 | 无重复（每个字符频次 ≤ 1） | 有重复时收缩 | 外层 for 末尾（最长） |
| 字符串排列 | 定长窗口频次匹配 | 定长窗口滑动（固定大小） | 每次滑动后检查 |
| 至多 K 个不同字符 | 不同字符数 ≤ k | 不同字符数 > k 时收缩 | 外层 for 末尾（最长） |
4.2 哈希表维护的两种方式
方式一：记录字符频次（char -> count），用 map.size() 或自定义计数器跟踪不同字符数
适用：需要统计不同字符数量，或需要知道每个字符的确切频次
方式二：记录字符的最近出现位置（char -> lastIndex），left 直接跳跃
适用：仅”无重复字符”这一特殊条件，代码更简洁但扩展性差
4.3 valid 计数器 vs Arrays.equals vs map.size()
| 技术 | 适用条件 | 每步更新代价 | 检查代价 |
|---|---|---|---|
valid 计数器 | 需要知道”有多少种字符频次满足 need” | ||
Arrays.equals | 定长字符集（如 26 个字母） | $O( | |
map.size() | 关注不同字符种类数量 | 摊销 |
第 5 章 面试中的常见陷阱
5.1 收缩时哈希表元素的删除时机
// 错误：先删后减
if (window.get(d) == 0) window.remove(d);
window.put(d, window.get(d) - 1); // 此时如果已经 remove，get 会返回 null，NPE！
// 正确：先减后检查
window.put(d, window.get(d) - 1);
if (window.get(d) == 0) window.remove(d); // 减到 0 时才从哈希表中删除哈希表中的元素在频次减为 0 时才删除，否则 map.size() 会偏大（包含了频次为 0 的字符），导致收缩条件判断错误。
5.2 valid 计数器的更新顺序
// 加入字符 in
window[in]++;
if (window[in] == need[in]) valid++; // 先加后检查
// 移除字符 out（顺序必须是：先检查，再减）
if (window[out] == need[out]) valid--; // 先检查（减之前还满足）
window[out]--; // 再减如果移除时先减再检查，window[out]-- 后变成 need[out] - 1，不等于 need[out]，valid 不会减少，导致 valid 偏大，提前认为窗口满足条件。
小结
本文将滑动窗口的维护状态从简单的”和”升级为”字符频次哈希表”，覆盖了三道高频面试题：
- 无重复字符最长子串：频次哈希表 + 重复时收缩；或最近下标哈希表 + 直接跳跃
- 字符串排列：定长窗口 +
valid计数器， 快速判断频次匹配 - 至多 K 个不同字符：“恰好 K 个”= “至多 K 个” - “至多 K-1 个”的差分技巧
下一篇是本专栏难度最高的一篇——最小覆盖子串（Minimum Window Substring），在此基础上处理多字符、多频次、多约束的最复杂滑动窗口场景。