1. 滑动窗口算法从入门到精通的实战指南如果你刷过一些算法题尤其是字符串和数组相关的题目大概率会碰到“滑动窗口”这个词。我第一次系统性地接触它是在解决“无重复字符的最长子串”这道经典题目时当时用暴力解法超时百思不得其解直到看到滑动窗口的思路才恍然大悟。它不是什么高深莫测的黑魔法而是一种极其高效、优雅的解题思想一旦掌握就能轻松解决一大类问题。简单来说滑动窗口就是在数组或字符串上维护一个连续的、大小可变或固定的子区间像一扇窗户一样从左滑到右在滑动的过程中高效地更新信息、寻找答案。它把许多看似需要O(n²)的暴力枚举问题优化到了O(n)的线性时间复杂度。今天我就结合自己刷题和面试的经验把这套方法的里里外外、各种变体以及实战中的坑给你彻底讲明白。2. 核心思想与适用场景拆解2.1 为什么需要滑动窗口在算法世界里效率是王道。很多问题要求我们在一个序列数组或字符串中找到一个满足特定条件的连续子区间。最笨的办法就是双重循环枚举所有可能的起点和终点然后检查每个子区间。假设序列长度为n这复杂度就是O(n²)当n很大时比如10^5计算量会爆炸。滑动窗口的精妙之处在于它利用了问题的两个特性来避免重复计算连续性我们寻找的是连续子序列而不是离散的子集。单调性当窗口滑动时窗口内的状态变化往往是渐进的、可预测的。例如寻找“和大于等于target的最短子数组”。暴力法需要计算所有子数组的和大量重复。而滑动窗口通过动态调整窗口的左右边界在移动时只需增加一个新元素或减少一个旧元素来更新窗口和避免了每次重新计算整个区间和的开销。这背后的思想本质上是“双指针”的一种高级应用通过两个指针左边界L和右边界R协同工作一前一后勾勒出这个动态的窗口。2.2 识别滑动窗口问题的“指纹”不是所有问题都适合用滑动窗口。我总结了几条特征当你看到题目描述出现这些关键词时就要立刻想到它连续子数组/子字符串这是最明显的信号。最小/最大长度例如“长度最小的子数组”、“最长的无重复字符子串”。满足某种条件如“和大于等于K”、“包含所有指定字符”。关键词“最长”、“最短”、“最多”、“最少”这些优化目标常常暗示可以用窗口滑动来高效搜索。从问题类型上看滑动窗口主要攻克以下几类固定长度窗口窗口大小k是给定的问题通常与窗口内的统计量和、最大值、平均值有关。可变长度窗口窗口大小需要动态调整以满足条件这是更常见也更灵活的类型用于寻找最优最长或最短子区间。计数型窗口常用于字符串匹配、异位词判断需要维护一个哈希表来记录窗口内字符的计数。单串滑动窗口在单个数组或字符串上操作是最基础的模型。多串滑动窗口例如判断一个字符串是否包含另一个字符串的所有字符需要在两个串之间建立联系。理解这些场景能帮助你在拿到新题时快速进行模式识别选择正确的解题框架。3. 算法框架与两种核心类型详解掌握滑动窗口关键在于吃透一套通用的代码框架并理解其两种主要变体。下面我给出一个高度抽象但极其实用的伪代码框架并附上详细的注释说明。3.1 通用框架与代码模板无论是固定窗口还是可变窗口其核心骨架是相通的。我习惯用左右指针left和right来定义窗口的边界[left, right)注意我通常使用左闭右开区间这样在初始时窗口为空left right 0处理起来更统一。def sliding_window_template(s: str or List[int]) - Any: # 初始化左右指针窗口通常定义为 [left, right) left, right 0, 0 # 用于记录窗口状态的变量如和、哈希表计数器等 window {} # 用于记录最终结果如最大长度、最小长度等 result 0 # 主循环右指针不断向右探索扩大窗口 while right len(s): # c 是将要进入窗口的元素 c s[right] # 右指针右移扩大窗口 right 1 # 更新窗口状态以反映新元素c的加入 # ... 进行一系列更新操作例如 window[c] 1 # *** 调试信息打印当前窗口状态实际解题时可删除*** # print(f窗口扩大: [{left}, {right}) 当前窗口状态: {window}) # 内层循环判断当前窗口是否满足收缩条件 # 对于可变窗口这里是关键对于固定窗口可能不需要或条件不同 while (window needs shrink): # d 是将要移出窗口的元素左边界指向的元素 d s[left] # 左指针右移收缩窗口 left 1 # 更新窗口状态以反映旧元素d的移除 # ... 进行一系列更新操作例如 window[d] - 1 # *** 调试信息打印当前窗口状态实际解题时可删除*** # print(f窗口收缩: [{left}, {right}) 当前窗口状态: {window}) # 在窗口的某个状态扩大后或收缩后更新最终答案 # 例如更新最大长度result max(result, right - left) # 注意更新答案的时机取决于具体问题 return result这个模板的精髓在于两个指针的移动节奏和窗口状态的维护。right负责探索和扩大窗口left负责在条件满足时收缩窗口以寻找最优解或使窗口重新有效。window变量是窗口的“记忆体”必须能以O(1)或极低的成本更新这是保证整体O(n)复杂度的关键。3.2 固定大小滑动窗口实战固定窗口问题相对直接窗口大小k是预先给定的。我们通常先初始化第一个窗口的状态然后让窗口每次向右滑动一格同时更新状态减去离开窗口的左端元素加上新进入窗口的右端元素。经典例题滑动窗口最大值LeetCode 239给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。这道题的难点在于如何高效地获取窗口内的最大值。如果每次滑动都重新遍历窗口求最大值复杂度是O(n*k)。我们的目标是O(n)。解决方案使用单调递减队列维护一个双端队列deque里面存储的是数组元素的索引并且保证队列头部到尾部对应的元素值是单调递减的。这样队列头部就是当前窗口的最大值。当窗口右移新元素加入时从队列尾部开始将所有小于新元素的索引弹出然后加入新元素索引。这保证了队列的单调性。当窗口左移需要移除元素时检查队列头部的索引是否已经不在窗口内即索引小于当前左边界如果是则将其从头部弹出。当窗口形成即right k-1后每次队列的头部索引对应的元素就是当前窗口的最大值。from collections import deque def maxSlidingWindow(nums: List[int], k: int) - List[int]: if not nums: return [] n len(nums) if k 1: return nums result [] # deque 中存储的是索引且对应元素值单调递减 dq deque() for right in range(n): # 1. 维护单调性移除所有小于当前元素的队尾索引 while dq and nums[dq[-1]] nums[right]: dq.pop() dq.append(right) # 2. 移除不在窗口内的队首索引 left right - k 1 if dq[0] left: dq.popleft() # 3. 当窗口大小达到k时记录结果 if right k - 1: result.append(nums[dq[0]]) return result实操心得固定窗口问题关键在于找到高效维护窗口核心“指标”如最大值、最小值、和、平均值的数据结构。除了单调队列前缀和也是固定窗口求和的利器。记住先暴力思考“窗口滑动时什么信息变了什么信息没变”再寻找能快速更新这些信息的方法。3.3 可变大小滑动窗口实战可变窗口更为灵活和常见窗口的扩张与收缩取决于当前窗口是否满足题目给定的条件。通常我们用一个while循环来收缩窗口直到窗口再次满足可以继续扩张的状态。经典例题无重复字符的最长子串LeetCode 3给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。这是可变窗口的入门必做题。我们需要一个窗口窗口内的所有字符都是唯一的。用右指针right探索一旦发现重复字符就必须移动左指针left直到重复字符被移出窗口。解决方案哈希表记录字符最新索引我们用一个字典char_index来记录每个字符最近一次出现的位置。右指针right不断右移。如果当前字符s[right]已经在字典中并且其记录的位置 left说明这个重复字符在当前窗口内那么就必须将左指针left移动到该重复字符上次出现位置的下一个位置从而将重复字符移出窗口。无论是否发生收缩都更新当前字符的最新位置到字典中。在每一步用right - left 1更新最大长度。def lengthOfLongestSubstring(s: str) - int: char_index {} # 存储字符 - 该字符最新出现的索引 left 0 max_len 0 for right in range(len(s)): current_char s[right] # 如果字符出现过且出现的位置在当前窗口内 left if current_char in char_index and char_index[current_char] left: # 收缩左边界直接跳到重复字符的下一个位置 left char_index[current_char] 1 # 更新或记录当前字符的最新位置 char_index[current_char] right # 计算当前窗口长度并更新答案 current_len right - left 1 max_len max(max_len, current_len) return max_len另一个经典例题最小覆盖子串LeetCode 76给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “”。这是可变窗口的进阶题需要维护一个更复杂的窗口状态窗口需要包含t的所有字符考虑重复次数。我们使用两个哈希表need记录t中每个字符需要的数量window记录当前窗口中对应字符的数量。再用一个变量valid记录当前窗口中已经满足need要求即数量大于等于所需的字符种类数。from collections import defaultdict def minWindow(s: str, t: str) - str: need defaultdict(int) window defaultdict(int) for c in t: need[c] 1 left, right 0, 0 valid 0 # 记录窗口中满足need条件的字符种类数 start, length 0, float(inf) # 记录最小子串的起始位置和长度 while right len(s): c s[right] right 1 # 更新窗口数据 if c in need: window[c] 1 if window[c] need[c]: # 该字符数量刚好达到要求 valid 1 # 判断左侧窗口是否要收缩当窗口已包含t的所有字符 while valid len(need): # 更新最小覆盖子串 if right - left length: start left length right - left # d是将移出窗口的字符 d s[left] left 1 # 更新窗口数据 if d in need: if window[d] need[d]: # 移出前刚好满足移出后就不满足了 valid - 1 window[d] - 1 return if length float(inf) else s[start:startlength]注意事项在可变窗口的收缩条件判断上一定要小心。while循环的条件是“当窗口不满足题目要求时要一直收缩吗”不恰恰相反。通常收缩条件是“当窗口满足或过度满足题目要求时我们尝试收缩以寻找更优解如更短的子串”。在“最小覆盖子串”中收缩条件是valid len(need)即窗口已经覆盖了所有目标字符此时我们尝试收缩左边界看是否能得到一个更短的、同样满足条件的子串。4. 高频题型实战与代码精讲理解了框架和类型我们通过几道高频且具有代表性的题目来深化对不同场景下滑动窗口应用的理解。我会带你一步步分析并给出注释详细的代码。4.1 长度最小的子数组LeetCode 209给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回 0 。思路分析 这是典型的可变窗口求最短长度问题。窗口状态是窗口内元素的和window_sum。我们不断扩大右边界增加和一旦window_sum target就记录当前窗口长度并尝试收缩左边界减少和以寻找更短的满足条件的子数组。收缩的条件是while window_sum target。def minSubArrayLen(target: int, nums: List[int]) - int: n len(nums) left, right 0, 0 window_sum 0 min_len float(inf) # 初始化为无穷大 while right n: # 扩大窗口加入右指针指向的元素 window_sum nums[right] right 1 # 当窗口和满足条件时尝试收缩窗口 while window_sum target: # 更新最小长度 current_len right - left # 因为right已1所以长度是right-left min_len min(min_len, current_len) # 收缩窗口移出左指针指向的元素 window_sum - nums[left] left 1 return 0 if min_len float(inf) else min_len关键点注意current_len right - left的计算。因为我们采用的是左闭右开区间[left, right)窗口内的元素索引是从left到right-1所以窗口长度就是right - left。这种边界处理方式在循环中非常清晰。4.2 字符串的排列LeetCode 567给你两个字符串 s1 和 s2 判断 s2 是否包含 s1 的排列。换句话说s1 的排列之一是 s2 的 子串。思路分析 判断s2是否包含一个子串这个子串是s1的某种排列。这意味着这个子串的长度固定为len(s1)且其中每个字符的出现次数与s1完全一致。这可以转化为一个固定长度的计数窗口问题。首先统计s1的字符计数need。在s2上维护一个长度为len(s1)的滑动窗口统计窗口内字符的计数window。比较window是否等于need。如果相等则找到。窗口滑动时需要更新window计数减去左端字符加上右端新字符。from collections import Counter def checkInclusion(s1: str, s2: str) - bool: len1, len2 len(s1), len(s2) if len1 len2: return False need Counter(s1) # s1的字符频率 window Counter() # 当前窗口的字符频率 # 初始化第一个窗口 [0, len1) for i in range(len1): window[s2[i]] 1 if window need: return True # 开始滑动窗口 for right in range(len1, len2): left_char s2[right - len1] # 将要离开窗口的字符 right_char s2[right] # 将要进入窗口的字符 # 更新窗口移出左字符加入右字符 window[left_char] - 1 if window[left_char] 0: # 如果计数为0删除该键便于后续比较 del window[left_char] window[right_char] 1 # 判断当前窗口是否匹配 if window need: return True return False优化技巧我们也可以使用类似“最小覆盖子串”中的valid变量来优化避免每次全量比较两个Counter。维护一个valid变量记录当前窗口中有多少种字符的数量已经满足need的要求。当valid等于need中不同字符的种类数时即找到答案。这种方法在字符串字符集较大时更高效。4.3 找到字符串中所有字母异位词LeetCode 438给定两个字符串 s 和 p找到 s 中所有 p 的字母异位词的子串返回这些子串的起始索引。思路分析 这道题是上一题“字符串的排列”的扩展不再是判断是否存在而是要找出所有起始位置。思路完全一致只是把“找到即返回”改为“记录所有符合条件的窗口左边界”。我们采用优化后的valid方法来实现。from collections import defaultdict def findAnagrams(s: str, p: str) - List[int]: need defaultdict(int) window defaultdict(int) for c in p: need[c] 1 left, right 0, 0 valid 0 result [] need_len len(need) # need中不同字符的种类数 while right len(s): c s[right] right 1 # 更新右指针字符进窗口 if c in need: window[c] 1 if window[c] need[c]: valid 1 # 当窗口大小等于p的长度时判断并尝试收缩 # 注意因为我们要找的是固定长度的异位词所以窗口大小固定为len(p) while right - left len(p): # 如果窗口大小刚好等于len(p)且valid满足则记录答案 if right - left len(p) and valid need_len: result.append(left) # 收缩左边界 d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return result踩坑记录在实现时内层while循环的条件是right - left len(p)这确保了窗口大小不会超过len(p)。当窗口大小等于len(p)时我们检查是否满足异位词条件 (valid need_len)。这里很容易错写成while valid need_len但这样收缩的条件是“窗口已经满足要求”而我们需要的是“当窗口达到固定大小时进行检查”两者逻辑不同。对于固定窗口问题更常见的写法是像“字符串的排列”例题那样用for循环控制右指针显式地管理窗口大小。5. 复杂场景与边界问题处理滑动窗口的思路清晰后真正的挑战往往来自于边界条件和复杂场景的变形。这部分内容教科书上很少讲却是在面试和竞赛中区分水平的关键。5.1 涉及负数或零的数组问题经典的滑动窗口算法通常假设数组元素为正数如“长度最小的子数组”这样窗口扩大则和增加收缩则和减少具有单调性。但当数组包含负数或零时这个性质被破坏了。窗口扩大和可能减少窗口收缩和可能增加。此时简单的双指针滑动可能失效。例题和等于K的最长子数组长度LeetCode 325 变种或 560的子数组和等于K给定一个整数数组和一个整数 k你需要找到该数组中和为 k 的连续子数组的最长长度。对于这个问题滑动窗口无法直接应用。因为存在负数右指针右移扩大窗口时和可能变小左指针右移收缩窗口时和可能变大指针移动没有确定的方向性。解决方案前缀和 哈希表这是处理子数组和问题的更通用武器。计算前缀和数组prefix_sum其中prefix_sum[i]表示从0到i-1的元素和。我们要找sum[i...j] k即prefix_sum[j1] - prefix_sum[i] k。转化一下对于每个位置j我们想找是否存在一个更早的位置i使得prefix_sum[i] prefix_sum[j1] - k。因此我们遍历数组用哈希表记录每个前缀和第一次出现的位置。在位置j检查prefix_sum[j1] - k是否在哈希表中如果在其对应的位置i与当前位置j就构成了一个和为k的子数组我们可以计算长度并更新最大值。def maxSubArrayLen(nums: List[int], k: int) - int: prefix_sum 0 sum_to_index {0: -1} # 初始化前缀和为0出现在索引-1即开始之前 max_len 0 for i, num in enumerate(nums): prefix_sum num # 如果我们需要的前缀和 (prefix_sum - k) 出现过 if (prefix_sum - k) in sum_to_index: # 当前索引 i 与 该前缀和出现的索引之间的子数组和为 k length i - sum_to_index[prefix_sum - k] max_len max(max_len, length) # 只记录前缀和第一次出现的位置以保证子数组最长 if prefix_sum not in sum_to_index: sum_to_index[prefix_sum] i return max_len核心要点当数组元素不全是正数时要警惕滑动窗口的适用性。前缀和哈希表是解决子数组和问题的更强大工具它将问题从“寻找一个区间”转化为“在历史中寻找一个特定的值”时间复杂度依然是O(n)。5.2 多指针与多维窗口有些问题窗口的状态不是一维的或者收缩条件涉及多个约束。这时可能需要维护多个指针或更复杂的数据结构。例题至多包含两个不同字符的最长子串LeetCode 159给定一个字符串 s 找出至多包含两个不同字符的最长子串的长度。窗口需要满足的条件是“不同字符数 2”。我们需要一个哈希表window_count来实时记录窗口内每个字符的出现次数以及一个变量distinct_count来记录当前窗口内不同字符的数量。右指针右移更新window_count和distinct_count。当distinct_count 2时收缩左指针直到distinct_count回到 2。在每一步更新最大长度。def lengthOfLongestSubstringTwoDistinct(s: str) - int: from collections import defaultdict left, right 0, 0 window_count defaultdict(int) distinct_count 0 max_len 0 while right len(s): c s[right] right 1 window_count[c] 1 if window_count[c] 1: # 新字符加入窗口 distinct_count 1 # 当不同字符数超过2时收缩窗口 while distinct_count 2: d s[left] left 1 window_count[d] - 1 if window_count[d] 0: # 一个字符从窗口中完全移除 distinct_count - 1 # 此时窗口满足条件更新答案 max_len max(max_len, right - left) return max_len这个模式可以推广到“至多包含K个不同字符的最长子串”LeetCode 340只需将判断条件中的2改为K即可。关键在于维护好窗口内字符的计数以及不同字符的个数。5.3 窗口状态维护的优化技巧窗口状态的更新必须是O(1)或近似O(1)的否则整体复杂度就会退化。除了使用哈希表在一些特殊情况下有更优的选择。字符集固定且较小如果字符串只包含小写英文字母可以使用长度为26的数组代替哈希表访问速度更快。need [0] * 26 window [0] * 26 # 字符c的索引ord(c) - ord(a)维护窗口极值如前所述使用单调队列维护窗口最大值/最小值。维护窗口有序性有时需要窗口内的元素保持某种顺序或快速获取中位数。可以使用平衡二叉搜索树如Python的sortedcontainers库或两个堆大顶堆和小顶堆来维护但这会增加复杂度通常用于更特殊的问题。6. 常见陷阱、调试技巧与面试要点即使理解了算法在实际编码和面试中还是会遇到各种问题。这里分享一些我踩过的坑和总结的经验。6.1 高频易错点排查清单指针移动与区间表示不统一这是最常见的错误。务必明确你定义的窗口区间是左闭右开[left, right)还是左闭右闭[left, right]并在计算长度、更新状态时保持一致。我强烈推荐使用左闭右开初始时leftright0表示空窗口逻辑更清晰。收缩条件判断错误收缩窗口的while循环条件写反。记住收缩是为了让窗口从“满足条件”变得“不满足条件”以寻找下一个可能满足的窗口或者从“不满足条件”变得“满足条件”的情况很少。多问自己我现在希望窗口保持什么状态状态更新顺序错误先移动指针还是先更新状态变量通常右指针移动后立即更新窗口状态加入新元素左指针移动前需要基于当前状态决定是否移动移动后立即更新状态移除旧元素。顺序错了状态就乱了。答案更新时机不当应该在窗口满足题目要求时更新答案。对于求最短长度通常在收缩窗口的循环内更新因为收缩时窗口仍满足条件且可能更短。对于求最长长度通常在收缩循环结束后更新因为此时窗口是满足条件的最长可能状态之一。务必结合具体题目分析。哈希表键的删除使用哈希表记录计数时当某个字符的计数减到0最好将其从哈希表中删除使用del或pop。这样在判断window need或比较valid时更准确也节省空间。6.2 实用的调试方法当你的滑动窗口代码结果不对时别急着怀疑人生可以按以下步骤排查打印日志法在指针移动和状态更新的关键位置插入打印语句输出left,right,window状态valid等变量。这是最直观的方法。while right len(s): c s[right] right 1 # ... 更新状态 print(f扩大后: left{left}, right{right}, window{dict(window)}, valid{valid}) while valid target_valid: # ... 更新答案和收缩 print(f收缩中: left{left}, right{right}, window{dict(window)}, valid{valid})小数据测试法不要用复杂的例子自己构造一个最小规模的测试用例比如数组[1,2,3], target3在纸上或心里一步步模拟代码执行跟踪每个变量的变化。对比暴力法写一个绝对正确的暴力解法O(n²)用于在小数据量上验证你的滑动窗口算法的输出是否正确。这是验证算法正确性的黄金标准。6.3 面试中的表达与思考在面试中考察滑动窗口不仅是为了得到正确答案更是为了考察你的沟通和问题分析能力。先澄清问题拿到题目先和面试官确认输入输出的细节、边界条件空数组、负数、大数据量等。从暴力法说起不要一上来就提滑动窗口。先说最直观的暴力解法通常是双重循环枚举所有子数组并分析其时间复杂度O(n²)和瓶颈所在。这展示了你的分析基础。引出优化思路指出暴力法的重复计算问题然后自然引出滑动窗口的思想“我们可以维护一个窗口在窗口滑动时只更新变化的部分从而避免重复计算。”描述算法框架清晰地定义左右指针left/right说明窗口的含义解释窗口如何扩大right右移和收缩left右移并强调状态维护哈希表、变量等是如何以O(1)时间更新的。讨论复杂度明确说出时间复杂度和空间复杂度。滑动窗口通常是O(n)时间O(k)或O(1)额外空间取决于字符集大小。手写代码按照你描述的框架写出整洁、有注释的代码。写完后用一个小例子口头跑一遍。思考变种如果时间允许可以讨论一下问题的变种比如数组包含负数怎么办引出前缀和哈希表或者如果要求的是“恰好K个不同字符”而不是“最多K个”这通常需要用到“最多K个”减去“最多K-1个”的技巧。这能展现你的知识深度。滑动窗口是一把锋利的算法武器理解其本质是“双指针”针对连续子区间问题的特化掌握其“扩大-收缩-更新”的节奏感并积累足够多的题型模式你就能在遇到相关问题时迅速识别并干净利落地解决。它没有动态规划那么变化多端也没有深度优先搜索那么需要递归思维但它以其简洁和高效在解决一类特定问题上几乎是无敌的。多练习多思考边界多总结模板背后的原理你就能把它变成自己的肌肉记忆。