1. 项目概述跟着灵神学算法系列是一个面向算法初学者的系统性学习项目Day1作为入门篇章重点聚焦滑动窗口这一基础但强大的算法技巧。作为算法竞赛和面试中的常客滑动窗口以其O(n)的时间复杂度优势成为处理子串、子数组问题的首选方案。我在实际刷题和算法教学中发现90%的初学者在首次接触滑动窗口时都会陷入暴力解法优化不来的困境。这个系列将采用问题驱动可视化演示的方式带你从LeetCode真题入手逐步掌握滑动窗口的三大应用场景和六种变形解法。2. 滑动窗口核心原理2.1 算法思想本质滑动窗口本质上是通过维护一个动态变化的区间避免重复计算来提升效率。就像用望远镜观察风景时我们不会每次移动都重新调整焦距而是保持镜筒平稳滑动。以经典的无重复字符的最长子串问题为例暴力解法需要O(n²)时间检查所有子串滑动窗口通过左右指针维护当前窗口只需O(n)即可完成扫描def lengthOfLongestSubstring(s: str) - int: char_index {} # 存储字符最后出现位置 left max_len 0 for right, char in enumerate(s): if char in char_index and char_index[char] left: left char_index[char] 1 char_index[char] right max_len max(max_len, right - left 1) return max_len2.2 两种基本类型固定长度窗口窗口大小保持不变典型问题字符串的排列组合检查实现要点右指针每次移动时同步移动左指针可变长度窗口窗口根据条件动态扩展/收缩典型问题满足条件的最短子数组实现要点需要维护窗口状态变量关键技巧使用哈希表记录窗口内元素频次时要注意处理计数为0的情况避免错误判断3. 实战应用解析3.1 字符串类问题例题最小覆盖子串LeetCode 76给定字符串S和T在S中找到包含T所有字符的最短子串。这个问题的难点在于需要处理字符重复出现的情况窗口收缩条件复杂def minWindow(s: str, t: str) - str: from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 need_cnt len(t) left 0 res (0, float(inf)) for right, c in enumerate(s): if need[c] 0: need_cnt - 1 need[c] - 1 if need_cnt 0: # 满足条件时收缩窗口 while True: c s[left] if need[c] 0: break need[c] 1 left 1 if right - left res[1] - res[0]: res (left, right) need[s[left]] 1 need_cnt 1 left 1 return s[res[0]:res[1]1] if res[1] float(inf) else 3.2 数组类问题例题和至少为K的最短子数组LeetCode 862这道题需要结合前缀和与单调队列实现滑动窗口计算前缀和数组pre_sum维护单调递增队列遍历时比较队列首尾差值def shortestSubarray(nums: List[int], k: int) - int: from collections import deque n len(nums) pre_sum [0] * (n 1) for i in range(n): pre_sum[i1] pre_sum[i] nums[i] q deque() res float(inf) for i in range(n1): while q and pre_sum[i] - pre_sum[q[0]] k: res min(res, i - q.popleft()) while q and pre_sum[i] pre_sum[q[-1]]: q.pop() q.append(i) return res if res ! float(inf) else -14. 常见问题与优化技巧4.1 边界条件处理空输入处理检查输入字符串/数组是否为空特殊处理长度为1的情况无效窗口判断当右指针到达末尾但窗口不满足条件时使用哨兵值简化判断逻辑4.2 性能优化策略哈希表预分配# 对于已知字符范围的情况如仅小写字母 count [0] * 26提前终止当找到理论最小窗口时立即返回在遍历中加入early break条件双指针同步移动某些情况下左右指针可以同步前进减少不必要的窗口收缩操作4.3 调试技巧可视化打印print(f窗口[{left}:{right}]: {s[left:right1]})状态检查assert sum(count.values()) right - left 1测试用例设计包含重复字符的字符串全相同元素的极端情况目标字符串包含不存在字符的情况5. 进阶训练建议掌握基础滑动窗口后建议按以下顺序进阶先刷完LeetCode滑动窗口标签下的所有简单题然后挑战中等难度经典题340.至多包含K个不同字符的最长子串424.替换后的最长重复字符992.K个不同整数的子数组最后尝试hard题目76.最小覆盖子串上文已解析239.滑动窗口最大值需结合单调队列我个人的训练心得是每天坚持3道滑动窗口变种题连续两周后会发现这类问题都有固定套路。建议准备错题本记录以下信息初始错误解法卡壳点分析最终AC代码时间/空间复杂度分析