滑动窗口思想概述
滑动窗口是双指针的一种特殊形态，专治 子串（子数组）相关的最优/判定问题。它维护一个左右指针（left 和 right）定义的窗口区间，通过不断移动右指针扩大窗口、移动左指针缩小窗口，在单次线性扫描中探索所有可能的可行解，从而避免暴力枚举所有子串的 O(n²) 开销。
滑动窗口的核心在于 窗口内数据状态的动态维护，通常借助哈希表或数组计数器记录窗口内元素的频次、种类、和等指标。当窗口满足某个条件时，尝试收缩左边界以寻找更优解，否则扩张右边界以包含更多元素。
LeetCode 热门 100 题中，有三道题是滑动窗口的经典代表：3. 无重复字符的最长子串（求最长满足条件的子串）、438. 找到字符串中所有字母异位词（求所有满足条件的子串起始位置）、76. 最小覆盖子串（求最短满足条件的子串）。它们覆盖了滑动窗口的三种主要题型：最长、所有、最短，掌握这三题即可应对绝大多数场景。
1. 无重复字符的最长子串（LeetCode 3）
题目：给定一个字符串 s，找出其中不含有重复字符的 最长子串 的长度。
暴力法：枚举所有子串，用哈希集合检查是否有重复字符，时间复杂度 O(n²)。
滑动窗口思路：
- 用右指针
right遍历字符串，将字符逐个加入窗口。 - 用哈希集合（或数组计数）记录窗口内出现过的字符。
- 当遇到重复字符时，左指针
left不断右移，并从集合中移除移出字符，直到窗口中不再有重复字符。 - 每次调整后，用当前窗口长度
right - left + 1更新最大值。
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
set.add(c);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
复杂度：O(n)，每个字符最多被加入和移出各一次，空间 O(min(m, n))（m 为字符集大小）。
关键点：while 循环处理重复，确保窗口内始终无重复字符；更新最大长度的时机在调整完成后。
2. 找到字符串中所有字母异位词（LeetCode 438）
题目：给定字符串 s 和 p，找到 s 中所有 p 的异位词的起始索引。异位词指字母种类和数量相同，顺序不限。
暴力法：枚举 s 中所有长度为 len(p) 的子串，统计字母频次比较，O(n * m)。
滑动窗口思路：窗口固定为 p.length() 大小，用右指针 right 移动，同时维护一个计数器数组记录窗口内各字母频次。当窗口长度正好等于 p.length() 时，比较窗口频次数组与 p 的频次数组是否相等，若相等则记录左指针。每次右移后，将新字符加入频次，并移除左指针指向的旧字符（保持窗口长度固定）。
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s.length() < p.length()) return res;
int[] pCount = new int[26];
int[] winCount = new int[26];
for (char c : p.toCharArray()) pCount[c - 'a']++;
int left = 0;
for (int right = 0; right < s.length(); right++) {
winCount[s.charAt(right) - 'a']++;
if (right - left + 1 > p.length()) {
winCount[s.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == p.length() && Arrays.equals(winCount, pCount)) {
res.add(left);
}
}
return res;
}
复杂度：O(n * 26) = O(n)，空间 O(1)（固定 26 长度）。
关键点：窗口长度固定，每次移动右指针后，若长度超出则移动左指针，保证窗口长度恰好为 m；比较频次数组可直接用 Arrays.equals。
3. 最小覆盖子串（LeetCode 76）
题目：给定字符串 s 和 t，在 s 中找到包含 t 中所有字符（包括重复字符）的 最短子串，若不存在返回空串。
难点：窗口需要动态伸缩，既要包含所有所需字符，又要尽量短。
滑动窗口思路：用哈希表 need 记录 t 中每个字符的需求数量，用 window 记录当前窗口内各字符出现次数。用 formed 记录当前窗口中满足需求（频次 >= need）的字符种类数，当 formed == need.size() 时，窗口已覆盖所有所需字符。此时尝试收缩左指针以缩小窗口，并不断更新最小长度和起始位置；收缩时若某个字符频次不满足需求，则 formed 减少。继续移动右指针扩大窗口。
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int formed = 0, required = need.size();
int minLen = Integer.MAX_VALUE, start = 0;
while (right < s.length()) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) {
formed++;
}
while (left <= right && formed == required) {
c = s.charAt(left);
if (right - left + 1 < minLen) {
minLen = right - left + 1;
start = left;
}
window.put(c, window.get(c) - 1);
if (need.containsKey(c) && window.get(c).intValue() < need.get(c).intValue()) {
formed--;
}
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
复杂度：O(n + m)，空间 O(k)（k 为字符集大小）。
关键点：formed 记录的是字符种类数（去重），只有当某个字符的窗口频次 恰好等于 需求频次时才增加，减少时机类似；收缩时先更新最小长度，再移出左字符，最后调整 formed。
三题对比与启发
| 题目 | 窗口大小 | 目标 | 收缩条件 | 记录时机 | 时间复杂度 |
|---|---|---|---|---|---|
| 无重复字符最长 | 动态（尽量大） | 求最大长度 | 窗口内出现重复 | 每次调整后 | O(n) |
| 字母异位词 | 固定 (len p) | 求所有起始位置 | 窗口大小 > len p | 窗口大小 == len p 且频次匹配 | O(n) |
| 最小覆盖子串 | 动态（尽量小） | 求最小长度 | 窗口满足覆盖 | 满足覆盖时 | O(n) |
共同本质：滑动窗口利用双指针同步移动，在右指针扩张、左指针收缩的过程中，只关注当前窗口的有效信息，通过状态变量（如计数、formed）避免每次重新统计窗口，将 O(n²) 的暴力枚举降为 O(n)。
不同侧重：
- 无重复字符：以"无重复"为约束，遇到冲突即收缩。
- 字母异位词：固定窗口长度，滑动比较频次。
- 最小覆盖子串：以"包含所有所需字符"为约束，满足后不断收缩找最短。
总结：滑动窗口模块的核心心法
滑动窗口的精髓在于用两个指针维护一个动态区间，并利用计数器或哈希表 O(1) 维护区间状态。所有题目都遵循"右指针扩大窗口找可行解，左指针缩小窗口优化解"的通用框架。
应用滑动窗口的通用模板：
- 定义窗口状态变量（计数器、频次数组、满足条件计数等）。
- 右指针 right 逐位移动，更新状态。
- 当窗口满足题目条件时（或触发收缩条件时），进入 while 循环，移动左指针 left 缩小窗口，同时更新答案（长度、起始位置等）。
- 在收缩过程中，同步更新窗口状态，直到条件不再满足。
掌握这三题，就能识别大多数滑动窗口变种（如固定窗口、可变窗口、求最值、求所有解）。面试中遇到子串相关题目，优先思考能否用滑动窗口 O(n) 解决。