1. 滑动窗口算法概述滑动窗口Sliding Window是算法领域中一种经典的优化技术主要用于处理数组或字符串的连续子序列问题。我第一次接触这个概念是在解决LeetCode上无重复字符的最长子串问题时当时暴力解法的时间复杂度高达O(n²)而采用滑动窗口后立即优化到O(n)。滑动窗口的核心思想是维护一个动态变化的窗口通过调整窗口的左右边界来高效地遍历数据。这种方法特别适合解决满足某条件的连续子数组/子串这类问题能够将许多原本需要嵌套循环的问题转化为单层循环。2. 滑动窗口基本原理与实现2.1 算法框架解析一个标准的滑动窗口实现通常包含以下要素窗口的左右指针left, right记录窗口状态的哈希表或变量结果存储变量以Python为例基础模板如下def sliding_window(s: str) - int: left 0 window {} # 记录窗口内字符出现次数 res 0 # 存储最终结果 for right in range(len(s)): # 右指针移动扩大窗口 window[s[right]] window.get(s[right], 0) 1 # 判断是否需要收缩窗口 while window需要收缩的条件: # 左指针移动缩小窗口 window[s[left]] - 1 if window[s[left]] 0: del window[s[left]] left 1 # 更新结果 res max(res, right - left 1) return res2.2 窗口移动的三种情况在实际应用中窗口的移动策略可以分为三类固定大小窗口窗口大小保持不变如计算长度为k的子数组的平均值可变大小求最大值窗口可以扩大或缩小寻找满足条件的最大窗口可变大小求最小值窗口可以扩大或缩小寻找满足条件的最小窗口提示可变窗口问题中确定何时收缩窗口是关键这通常与问题的具体条件相关。3. 经典问题实战解析3.1 无重复字符的最长子串这是滑动窗口最经典的入门题LeetCode 3。给定一个字符串找出不含有重复字符的最长子串的长度。def lengthOfLongestSubstring(s: str) - int: left 0 char_index {} # 记录字符最后出现的位置 max_len 0 for right in range(len(s)): if s[right] in char_index: # 确保left不会回退 left max(left, char_index[s[right]] 1) char_index[s[right]] right max_len max(max_len, right - left 1) return max_len关键点使用字典记录字符最后出现的位置left指针的移动要取最大值避免回退每次右指针移动后都更新结果3.2 最小覆盖子串这是一个典型的可变窗口求最小值问题LeetCode 76。给定字符串S和T在S中找出包含T所有字符的最小子串。from collections import defaultdict def minWindow(s: str, t: str) - str: need defaultdict(int) for c in t: need[c] 1 left 0 missing len(t) # 还需要匹配的字符总数 min_len float(inf) res for right in range(len(s)): if s[right] in need: if need[s[right]] 0: missing - 1 need[s[right]] - 1 while missing 0: # 窗口满足条件 if right - left 1 min_len: min_len right - left 1 res s[left:right1] if s[left] in need: need[s[left]] 1 if need[s[left]] 0: missing 1 left 1 return res优化技巧使用missing变量避免每次检查整个need字典在收缩窗口时先更新结果再移动左指针使用defaultdict简化边界条件处理4. 滑动窗口的变种与应用4.1 固定大小窗口问题计算大小为k的连续子数组的最大平均值LeetCode 643def findMaxAverage(nums: List[int], k: int) - float: window_sum sum(nums[:k]) max_sum window_sum for i in range(k, len(nums)): window_sum nums[i] - nums[i-k] max_sum max(max_sum, window_sum) return max_sum / k特点窗口大小固定为k使用减头加尾的技巧避免重复计算时间复杂度从O(n*k)优化到O(n)4.2 计数类滑动窗口字符串的排列LeetCode 567。判断s2是否包含s1的排列from collections import defaultdict def checkInclusion(s1: str, s2: str) - bool: need defaultdict(int) for c in s1: need[c] 1 left 0 missing len(s1) for right in range(len(s2)): if s2[right] in need: if need[s2[right]] 0: missing - 1 need[s2[right]] - 1 if right len(s1): left_char s2[left] if left_char in need: need[left_char] 1 if need[left_char] 0: missing 1 left 1 if missing 0: return True return False注意事项窗口大小固定为s1的长度需要精确匹配字符出现次数使用missing变量优化判断逻辑5. 滑动窗口的优化技巧5.1 哈希表优化对于字符类问题如果输入确定是ASCII字符可以用数组代替哈希表def lengthOfLongestSubstring(s: str) - int: last_index [-1] * 128 # ASCII字符集 left 0 max_len 0 for right in range(len(s)): char ord(s[right]) left max(left, last_index[char] 1) last_index[char] right max_len max(max_len, right - left 1) return max_len优势数组访问比哈希表更快适用于字符集有限的情况代码更简洁5.2 前缀和结合滑动窗口解决子数组和等于k的问题LeetCode 560from collections import defaultdict def subarraySum(nums: List[int], k: int) - int: prefix_sum defaultdict(int) prefix_sum[0] 1 current_sum 0 count 0 for num in nums: current_sum num count prefix_sum.get(current_sum - k, 0) prefix_sum[current_sum] 1 return count关键点使用前缀和避免重复计算哈希表记录前缀和出现次数注意初始化prefix_sum[0] 16. 常见错误与调试技巧6.1 指针移动顺序错误一个常见错误是在收缩窗口前忘记更新结果。正确的顺序应该是更新结果移动左指针更新窗口状态错误示例while 窗口需要收缩: left 1 # 先移动指针 res max(res, right-left1) # 后更新结果6.2 边界条件处理在处理字符串问题时特别要注意空字符串和单字符的情况。例如在无重复字符的最长子串中输入应该返回0输入a应该返回16.3 窗口状态更新不及时另一个常见问题是忘记在移动指针时更新窗口状态。例如在最小覆盖子串问题中移动左指针时需要恢复need字典中的计数如果需要更新missing计数7. 滑动窗口问题分类训练7.1 字符串类问题最长无重复子串已介绍最小覆盖子串已介绍字符串排列已介绍找到字符串中所有字母异位词LeetCode 438最长重复字符替换LeetCode 4247.2 数组类问题最大连续1的个数IIILeetCode 1004水果成篮LeetCode 904乘积小于K的子数组LeetCode 713最短子数组和至少为kLeetCode 862大小为K且平均值大于阈值的子数组数LeetCode 13437.3 进阶挑战题滑动窗口最大值LeetCode 239最少交换次数来组合所有的1LeetCode 1151替换后的最长重复字符LeetCode 424K个不同整数的子数组LeetCode 992尽可能使字符串相等LeetCode 12088. 滑动窗口的时间复杂度分析滑动窗口算法最吸引人的特点是其高效的时间复杂度。对于大多数问题暴力解法通常需要O(n²)或O(n³)的时间复杂度滑动窗口优化到O(n)或O(n*k)其中k是字符集大小以无重复字符的最长子串为例每个元素最多被左右指针各访问一次哈希表操作是O(1)因此总体时间复杂度是O(n)空间复杂度方面通常需要O(k)的额外空间k是字符集大小对于ASCII问题可以认为是O(1)对于Unicode问题最坏情况是O(n)9. 滑动窗口与其他算法的比较9.1 与双指针的区别滑动窗口可以看作是一种特殊的双指针技术但有以下区别滑动窗口关注的是窗口内的所有元素双指针可能只关注指针所指的两个元素滑动窗口通常维护窗口的状态信息9.2 与动态规划的关系某些滑动窗口问题可以用动态规划解决但滑动窗口通常实现更简单空间复杂度更低适用于连续子序列问题例如最大子数组和问题LeetCode 53动态规划解法需要O(n)空间滑动窗口Kadane算法只需要O(1)空间10. 滑动窗口的实战技巧先写暴力解法理解问题本质后再优化明确窗口含义清楚定义窗口左右边界的含义画图辅助在纸上画出窗口移动过程测试边界条件空输入、单元素、全相同元素等情况逐步调试打印窗口状态和指针位置帮助理解在实际面试中我建议按照以下步骤明确问题是否适合滑动窗口定义窗口和需要维护的状态写出基本框架处理边界条件优化代码结构