一、什么是滑动窗口问题
想象你在公交车上透过窗户看风景，窗户固定大小，随着车子移动，你会看到不同的景色。滑动窗口问题也是这样——在数组或字符串中维护一个固定或可变大小的"窗口"，通过移动窗口来高效处理数据。这类问题通常要求我们找到满足特定条件的子数组或子串，比如最大和子数组、最小覆盖子串等。
滑动窗口的核心思想是避免重复计算。比如要计算长度为k的连续子数组最大和，暴力解法需要O(n*k)时间复杂度，而滑动窗口可以优化到O(n)。这就像你买菜时，老板不用每次都重新称重，只需要在前一次的基础上增减变化的部分。
二、双指针如何实现滑动窗口
双指针是滑动窗口的骨架。通常用left和right两个指针标记窗口边界，根据条件动态调整窗口大小。来看一个典型例子（使用Java语言示例）：
// 寻找最长无重复字符的子串长度
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 当遇到重复字符时，移动左指针缩小窗口
while (window.contains(c)) {
window.remove(s.charAt(left++));
}
window.add(c);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
/* 代码解析：
1. HashSet记录当前窗口字符
2. right指针主动向右扩展
3. 发现重复时，left指针被动右移
4. 实时更新最大窗口尺寸 */
再来看一个可变窗口的例子——求数组中和≥target的最短子数组：
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right]; // 扩展右边界
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++]; // 收缩左边界
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
/* 关键点：
1. 外层循环扩展窗口
2. 内层while满足条件时收缩窗口
3. 实时记录最小满足条件的窗口 */
三、滑动窗口的三大应用场景
1. 固定大小窗口
比如计算大小为k的窗口中的最大值。这时可以用单调队列优化：
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// 移除超出窗口范围的元素
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 维护单调递减队列
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
// 记录窗口最大值
if (i >= k - 1) {
res[i - k + 1] = nums[deque.peekFirst()];
}
}
return res;
}
/* 技术要点：
1. 队列存储的是索引而非值
2. 严格保持队列头部是当前窗口最大值
3. 双while结构保证队列单调性 */
2. 可变大小窗口
典型如字符串匹配问题。假设要在s中找到包含t所有字符的最小子串：
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// 初始化need字典
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, valid = 0;
int start = 0, len = Integer.MAX_VALUE;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 当窗口满足条件时尝试收缩
while (valid == need.size()) {
if (right - left + 1 < len) {
start = left;
len = right - left + 1;
}
char d = s.charAt(left++);
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
/* 实现要点：
1. 使用valid计数器避免频繁比较两个map
2. 收缩窗口时先检查是否可能更新结果
3. 注意Integer对象的比较要用equals */
3. 计数类问题
比如给定二进制数组，求包含相同数量0和1的最长子数组：
public int findMaxLength(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // 初始前缀和为0的索引
int count = 0, maxLen = 0;
for (int i = 0; i < nums.length; i++) {
count += (nums[i] == 1 ? 1 : -1);
if (map.containsKey(count)) {
maxLen = Math.max(maxLen, i - map.get(count));
} else {
map.put(count, i);
}
}
return maxLen;
}
/* 技巧：
1. 将0视为-1转化为求和为0的问题
2. 使用哈希表记录前缀和首次出现位置
3. 相同前缀和之间的子数组满足条件 */
四、技术优缺点与注意事项
优势分析
- 时间复杂度低：多数滑动窗口问题都能从O(n²)优化到O(n)
- 空间效率高：通常只需要常数或线性额外空间
- 代码简洁：模板化结构容易记忆和实现
局限性
- 适用场景有限：主要适用于连续子数组/子串问题
- 边界条件复杂：窗口移动时的边界处理容易出错
- 数据要求严格：通常需要数据具有单调性或特定规律
常见踩坑点
- 指针移动时机：该移动left时没移动会导致窗口过大，不该移动时移动会导致错过解
- 哈希表使用：当使用HashMap记录状态时，注意Integer对象的比较问题
- 初始值设置：如maxLen初始应为Integer.MIN_VALUE，minLen应为Integer.MAX_VALUE
调试技巧
- 打印窗口左右边界和关键变量
- 对特殊用例手动模拟运行过程
- 使用可视化工具观察窗口变化
五、总结与进阶思考
滑动窗口就像是一个智能的扫描仪，它不会重复检查已经确认过的区域，而是聪明地根据当前情况调整扫描范围。掌握这个技巧后，你会发现很多看似复杂的问题都能迎刃而解。
在实际面试中，滑动窗口类题目出现频率极高。建议重点练习：
- 无重复字符的最长子串（高频经典）
- 最小覆盖子串（综合难度较高）
- 字符串排列（固定窗口代表）
- 最大连续1的个数（简单但易错）
- 替换后的最长重复字符（需要技巧转换）
记住，所有滑动窗口问题都遵循相同模式：扩展右边界→满足条件时处理→收缩左边界→更新结果。把这个模式内化后，你就能快速识别并解决这类问题。
评论