1. 项目概述滑动窗口不止于“滑动”如果你刷过LeetCode或者准备过技术面试对“滑动窗口”这个词一定不陌生。它频繁出现在字符串、数组相关的题目中比如“无重复字符的最长子串”、“找到字符串中所有字母异位词”、“最小覆盖子串”等等。很多教程会告诉你滑动窗口就是维护一个左指针l和一个右指针r然后根据条件移动它们。这没错但如果你只理解到这个层面在实际编码时依然会感到困惑什么时候该移动右指针什么时候该收缩左指针窗口内的数据状态如何高效维护为什么我的解法总是超时滑动窗口本质上是一种基于双指针的优化思想它通过维护一个动态的、连续的区间窗口来避免暴力枚举中大量的重复计算。其核心价值在于它能将一些看似需要O(n²)甚至O(n³)时间复杂度的问题优化到O(n)。今天我们不谈枯燥的理论直接从几个经典的、有梯度的Python实战案例入手拆解滑动窗口的四种典型“套路”并分享我踩过无数坑后总结出的调试技巧和思维模板。无论你是正在入门算法的新手还是想深化理解的开发者这篇内容都能让你对滑动窗口有一个“肌肉记忆”级的掌握。2. 滑动窗口的四种核心套路与实战拆解滑动窗口问题虽然变化多端但根据窗口长度是否固定、收缩条件是否明确可以归纳为几种经典模式。理解这些模式相当于掌握了解题的“公式”。2.1 套路一固定长度窗口——最直接的“尺子”这是最简单的一种。窗口大小k是预先给定的我们的任务就是让这个固定长度的窗口从数组或字符串的起始位置滑动到末尾并在每个位置计算窗口内的某个统计量如和、最大值、字符频率等。经典例题给定一个整数数组nums和一个整数k找出滑动窗口大小为k时窗口内元素的最大值。暴力法的思维陷阱新手可能会对每个窗口都重新遍历其中的k个元素找最大值时间复杂度为O(n*k)。当n和k都很大时这无法接受。滑动窗口优化思路关键在于当窗口滑动时只有两个元素发生变化离开窗口的左端元素和进入窗口的右端元素。我们需要一个数据结构能快速获取当前窗口的最大值并且在元素离开窗口时能高效地将其移除。双端队列deque是完美选择。Python实现与逐行解析from collections import deque def max_sliding_window(nums, k): 使用单调递减队列维护窗口最大值。 队列中存储的是元素的索引且对应元素值从队首到队尾递减。 if not nums or k 0: return [] result [] window deque() # 存储的是索引 for i, num in enumerate(nums): # 1. 维护队列的单调递减性如果当前元素大于队尾元素则不断弹出队尾 while window and nums[window[-1]] num: window.pop() # 将当前元素索引加入队尾 window.append(i) # 2. 移除已经滑出窗口的队首元素索引 if window[0] i - k: window.popleft() # 3. 当窗口长度达到k时开始记录结果队首元素即为当前窗口最大值索引 if i k - 1: result.append(nums[window[0]]) return result # 测试 nums [1, 3, -1, -3, 5, 3, 6, 7] k 3 print(max_sliding_window(nums, k)) # 输出: [3, 3, 5, 5, 6, 7]关键操作解析while window and nums[window[-1]] num: window.pop()这保证了队列是“单调递减”的。任何比当前新元素num小的旧元素都不可能再成为后续窗口的最大值因为num比它们大且比它们更晚离开窗口所以可以直接淘汰。if window[0] i - k: window.popleft()检查队首当前最大值的索引是否已经不在当前窗口范围内即索引小于等于i-k如果是则弹出。这是保证窗口范围正确的关键。if i k - 1:当右指针i移动到索引k-1时窗口第一次成型此后每次循环都可以记录一个结果。实操心得固定窗口的“前k项初始化”技巧对于固定窗口还有一种常见的写法是先用一个循环初始化第一个窗口的状态然后再开始滑动。例如先计算前k个元素的和或频率。这种写法逻辑更清晰尤其适用于窗口状态比较复杂如需要维护哈希表计数的情况。上面的单调队列写法更精妙但理解门槛稍高。根据问题复杂度选择最清晰的实现方式比追求“一行代码”更重要。2.2 套路二可变长度窗口求最长/最大——尽量扩张必要时收缩这是面试中最常见的一类。题目通常要求找到一个满足某些条件的最长子数组或子串。窗口从0开始我们总是尝试向右移动右指针r来扩大窗口以期找到更长的解。同时我们需要一个条件来判断当前窗口是否“合法”。当窗口变得“不合法”时我们就移动左指针l来收缩窗口直到它重新变得“合法”。经典例题给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。思维过程目标最长的不重复子串。策略右指针r探索新字符扩大窗口。用一个集合set或字典记录字符最新索引来快速判断字符是否重复。收缩条件当r指向的字符已经在当前窗口中出现过即发生重复窗口变得“不合法”。此时必须移动左指针l将重复字符及其之前的字符移出窗口直到重复被消除。Python实现使用集合def length_of_longest_substring(s: str) - int: char_set set() l 0 max_length 0 for r in range(len(s)): # 当前右指针字符 s[r] # 如果字符已在集合中说明重复需要收缩左边界 while s[r] in char_set: char_set.remove(s[l]) # 移除左指针字符 l 1 # 左指针右移 # 此时窗口 s[l:r1] 中无重复字符 char_set.add(s[r]) # 将当前字符加入集合 # 更新最大长度 max_length max(max_length, r - l 1) return max_length # 测试 print(length_of_longest_substring(abcabcbb)) # 输出: 3 (abc) print(length_of_longest_substring(bbbbb)) # 输出: 1 (b) print(length_of_longest_substring(pwwkew)) # 输出: 3 (wke)为什么用while而不是if这是新手常犯的错误。当s[r]重复时只收缩一次l 1可能不足以消除重复因为重复的字符可能不是窗口左端的那个。例如字符串“abca”当r指向最后一个‘a‘时重复字符是开头的‘a‘。用if只移动一次l到‘b‘集合里还有{‘b‘, ‘c‘, ‘a‘}仍然重复。必须用while循环持续收缩直到将第一个‘a‘移出集合。2.3 套路三可变长度窗口求最短/最小——找到合法窗口后积极收缩这类问题要求找到一个满足条件的最短子数组或子串。思路与求最长类似但策略更积极一旦找到一个“合法”窗口我们就不再盲目扩张右边界而是尝试收缩左边界看看能否在保持“合法”的前提下得到一个更短的窗口并记录这个更短的长度。经典例题给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和≥ target的长度最小的连续子数组并返回其长度。思维过程目标和 ≥ target 的最短子数组。策略右指针r探索扩大窗口并累加和window_sum。收缩时机一旦window_sum target我们就找到了一个合法窗口。此时立即尝试收缩左边界l在保持window_sum target的前提下尽可能右移l以得到更短的窗口。每次收缩后都更新最小长度。记录结果在收缩过程中记录得到的最小窗口长度。Python实现def min_sub_array_len(target: int, nums) - int: l 0 window_sum 0 min_len float(inf) # 初始化为无穷大 for r in range(len(nums)): window_sum nums[r] # 扩大窗口加入右指针元素 # 当窗口和满足条件时尝试收缩窗口 while window_sum target: # 更新最小长度 current_len r - l 1 min_len min(min_len, current_len) # 收缩窗口减去左指针元素左指针右移 window_sum - nums[l] l 1 # 如果min_len没有被更新过说明没有符合条件的子数组返回0 return min_len if min_len ! float(inf) else 0 # 测试 print(min_sub_array_len(7, [2,3,1,2,4,3])) # 输出: 2 ([4,3]) print(min_sub_array_len(11, [1,1,1,1,1,1,1,1])) # 输出: 0注意事项内外循环的对称性在“求最长”问题中内层while循环用于使窗口从不合法变为合法收缩直到合法。在“求最短”问题中内层while循环用于使窗口从合法变为不合法收缩直到刚好不合法前一个状态就是最短合法窗口。理解这个对称性能帮你快速判断该用while还是if以及循环条件是什么。2.4 套路四计数型窗口与哈希表维护——频率才是关键很多滑动窗口问题其“合法性”条件不是简单的和或重复字符而是基于字符或数字的频率。例如“找到字符串中所有字母异位词”、“最小覆盖子串”。这类问题的核心是维护两个哈希表或频率数组一个记录目标need一个记录当前窗口window并维护一个变量来跟踪当前窗口中有多少字符已经满足了目标频率要求valid。经典例题给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。思维拆解目标定义异位词意味着子串和p的长度相同且各个字符的出现次数相同。数据结构need字典记录p中每个字符需要的次数。window字典记录当前窗口中属于p的字符的出现次数。valid变量记录当前窗口中有多少种字符的出现次数已经达到了need要求。窗口移动逻辑右扩r右移字符c进入窗口。如果c在need中则增加window[c]。如果window[c]等于need[c]则valid。左缩当窗口长度大于len(p)时需要收缩。l右移字符d离开窗口。如果d在need中则需要先检查window[d]是否等于need[d]是则valid--然后再减少window[d]。结果记录在每次右扩后检查当前窗口长度是否等于len(p)且valid是否等于need中字符的种类数。如果都满足则l就是一个合法起始索引。Python实现from collections import Counter, defaultdict def find_anagrams(s: str, p: str): need Counter(p) # 目标字符频率 window defaultdict(int) # 窗口字符频率 l, r 0, 0 valid 0 # 窗口中满足need条件的字符种类数 result [] while r len(s): c s[r] r 1 # 右指针移动 # 进行窗口内数据的一系列更新 if c in need: window[c] 1 if window[c] need[c]: valid 1 # 判断左侧窗口是否要收缩当前窗口长度 目标字符串长度时 while r - l len(p): # 当窗口符合条件时记录结果 if valid len(need): # 所有字符种类都满足要求 result.append(l) # 将要移出窗口的字符 d s[l] l 1 # 左指针移动 # 进行窗口内数据的一系列更新 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return result # 测试 print(find_anagrams(cbaebabacd, abc)) # 输出: [0, 6] print(find_anagrams(abab, ab)) # 输出: [0, 1, 2]为什么需要valid变量如果不使用valid每次判断窗口是否合法都需要遍历need字典比较window和need的每个计数是否相等时间复杂度为O(26)或O(128)字符集大小虽然常数级但不够优雅。使用valid变量我们可以在O(1)时间内判断窗口是否满足所有字符的频率要求这是典型的以空间换时间的优化思想也是滑动窗口结合哈希表的精髓所在。3. 滑动窗口的通用解题框架与调试技巧经过上面几种套路的分析我们可以提炼出一个适用于大多数滑动窗口问题的通用框架。掌握这个框架相当于有了一个可靠的解题模板。3.1 四步通用框架模板以下是一个用Python实现的、高度抽象的滑动窗口框架涵盖了可变窗口求最值问题的核心逻辑。def sliding_window_template(s, t): # 初始化窗口左右指针、结果变量、窗口状态容器如哈希表、和、计数器等 l, r 0, 0 result ... # 可能是长度、列表等 window_state ... # 如window_sum 0, window_dict {}, window_set set() # 外层循环移动右指针探索整个区间 while r len(s): # 1. 将s[r]加入窗口更新窗口状态 # 例如window_sum s[r], window_dict[s[r]] 1, window_set.add(s[r]) update_state_add(s[r]) # 2. 内层循环根据条件判断是否需要收缩左指针 # 条件可能是窗口状态不合法、窗口长度超标、找到了一个可行解需要优化等 while condition_to_shrink(window_state): # 3. 在收缩前可能需要基于当前窗口更新最终结果 # 例如更新最小/最大长度记录子串等 update_result_if_needed() # 4. 将s[l]移出窗口更新窗口状态左指针右移 update_state_remove(s[l]) l 1 # 右指针右移准备下一轮循环 r 1 return result框架使用要点condition_to_shrink这是区分不同问题的关键。对于“求最长”条件通常是“窗口不合法”对于“求最短”条件通常是“窗口合法”。update_result_if_needed更新结果的时机也很重要。有时在收缩循环内更新如求最短有时在收缩循环外更新如求最长且合法时。指针移动顺序框架中r和l的移动是交错进行的。通常是r先移动扩大窗口然后根据条件用while移动l收缩窗口。确保指针永不回退单调移动这是O(n)复杂度的保证。3.2 调试与思维验证技巧即使有了框架写出代码后也可能遇到各种边界错误。分享几个我常用的调试方法打印窗口状态法在循环关键位置打印l,r,window_state如哈希表、和等。while r len(s): # ... 更新状态 print(f”l{l}, r{r}, window{window_state}, valid{valid}“) while condition_to_shrink: # ... 更新结果和状态 print(f” Shrink: l{l}, new_window{window_state}“)通过观察打印日志可以清晰看到窗口是如何扩张和收缩的快速定位逻辑错误。小数据暴力对比法对于复杂的滑动窗口逻辑可以用最朴素的暴力算法双重循环枚举所有子串在小数据集如长度20上运行将结果与你优化后的滑动窗口算法结果进行对比。这是验证算法正确性的黄金标准。边界条件手动模拟法在脑子里或纸上手动模拟算法在极端情况下的运行。空输入s”“,target0等。无解情况数组全部元素和仍小于target。解在两端最小子数组就是整个数组最长子串就是整个字符串。重复元素处理在哈希表更新时valid的加减是否与window[c] need[c]的判断严格对应这是最容易出错的地方。复杂度自检问自己每个元素每个s[r]和s[l]被放入窗口和移出窗口的操作是常数时间吗每个元素是否最多被访问两次一次被r访问一次被l访问如果答案是肯定的那么你的算法时间复杂度就是O(n)。4. 从LeetCode经典题到实战变种掌握了核心套路和框架后我们可以挑战一些更复杂的变种问题它们往往是对基本套路的组合或条件升级。4.1 变种一带有“成本”约束的窗口例题给你一个二进制数组nums和一个整数k你需要将其中最多k个0翻转成1请返回仅包含1的最长子数组的长度。问题转化这不再是简单的“无重复”或“和大于某值”而是“窗口内最多允许有k个0”。我们可以把问题转化为寻找一个最长的子数组其中包含的0的个数不超过k个。滑动窗口思路窗口状态记录当前窗口中0的个数zero_count。右扩r右移如果nums[r] 0则zero_count 1。收缩条件当zero_count k时窗口不合法需要收缩。左缩移动l如果nums[l] 0则zero_count - 1直到zero_count k。更新结果在每次右扩后且收缩完成后窗口都是合法的此时用r - l更新最大长度。def longest_ones(nums, k): l 0 zero_count 0 max_len 0 for r in range(len(nums)): if nums[r] 0: zero_count 1 while zero_count k: # 不合法需要收缩 if nums[l] 0: zero_count - 1 l 1 # 此时窗口合法 max_len max(max_len, r - l 1) return max_len4.2 变种二多条件与数据结构维护例题给你一个字符串s请你找出至多包含两个不同字符的最长子串的长度。思路分析窗口合法性条件变成了“包含不同字符的个数”。我们需要一个数据结构来高效地维护窗口中字符的频率并能快速知道当前有多少个不同的字符。哈希表字典仍然是首选。滑动窗口实现def length_of_longest_substring_two_distinct(s: str) - int: from collections import defaultdict l 0 char_count defaultdict(int) max_len 0 for r in range(len(s)): # 右指针字符进入窗口 char_count[s[r]] 1 # 收缩条件窗口中不同字符数大于2 while len(char_count) 2: # 左指针字符移出窗口 char_count[s[l]] - 1 if char_count[s[l]] 0: # 如果某个字符计数为0则从字典中删除 del char_count[s[l]] l 1 # 更新最大长度 max_len max(max_len, r - l 1) return max_len关键点在收缩时不仅要将左指针字符的计数减1当计数减到0时必须将其从字典中删除这样才能保证len(char_count)准确反映窗口中真正存在的不同字符数。这是使用哈希表维护计数型窗口时的一个经典细节。4.3 避坑指南滑动窗口的常见“天坑”指针移动与状态更新的顺序是先移动指针还是先更新状态顺序错了整个逻辑就乱了。我的经验法则是“右扩先更新左缩先判断”。即右指针移动后立即更新窗口状态加入新元素在左指针移动前先基于当前状态判断是否需要收缩如果需要则先更新结果如果需要再更新状态移除旧元素最后移动指针。while与if的误用这是最大的思维误区。记住一个原则当你无法确定收缩一次就能使窗口重新满足条件时就用while。在“无重复字符最长子串”中收缩一次可能移不掉重复字符在“和大于target的最短子数组”中收缩一次后可能和仍然大于target。在这些情况下必须用while循环持续收缩。窗口长度计算窗口长度通常是r - l 1当r和l是闭区间索引时或r - l当r是开区间索引指向下一个待处理元素时。在通用框架中我习惯使用while r len(s)和s[r]此时r是当前元素索引窗口长度为r - l 1。保持一致即可。哈希表valid变量的维护在频率问题中valid的增减必须与window[c] need[c]和window[c] need[c] - 1这样的精确判断绑定。增加时是在window[c] need[c]之后减少时是在window[c] need[c]之时。顺序反了就会计数错误。初始化和边界对于求最小值的问题结果初始值通常设为float(‘inf’)对于求最大值设为0或float(‘-inf’)。循环结束后要检查结果是否被更新过并返回合理的默认值如0。滑动窗口算法之所以强大在于它将一个复杂的问题转化为了指针的单调移动和窗口状态的增量更新。理解其本质是“双指针”的进阶并熟练掌握固定窗口、可变窗口求最长/最短、计数窗口这几种模式再配合通用的思维框架和细致的调试你就能攻克面试中绝大多数与之相关的难题。真正的掌握来自于将模板内化后对具体问题条件的准确翻译和映射。多练习多总结你会在代码中感受到这种算法之美。
滑动窗口算法详解：四种核心套路与Python实战
发布时间：2026/8/1 15:00:42
1. 项目概述滑动窗口不止于“滑动”如果你刷过LeetCode或者准备过技术面试对“滑动窗口”这个词一定不陌生。它频繁出现在字符串、数组相关的题目中比如“无重复字符的最长子串”、“找到字符串中所有字母异位词”、“最小覆盖子串”等等。很多教程会告诉你滑动窗口就是维护一个左指针l和一个右指针r然后根据条件移动它们。这没错但如果你只理解到这个层面在实际编码时依然会感到困惑什么时候该移动右指针什么时候该收缩左指针窗口内的数据状态如何高效维护为什么我的解法总是超时滑动窗口本质上是一种基于双指针的优化思想它通过维护一个动态的、连续的区间窗口来避免暴力枚举中大量的重复计算。其核心价值在于它能将一些看似需要O(n²)甚至O(n³)时间复杂度的问题优化到O(n)。今天我们不谈枯燥的理论直接从几个经典的、有梯度的Python实战案例入手拆解滑动窗口的四种典型“套路”并分享我踩过无数坑后总结出的调试技巧和思维模板。无论你是正在入门算法的新手还是想深化理解的开发者这篇内容都能让你对滑动窗口有一个“肌肉记忆”级的掌握。2. 滑动窗口的四种核心套路与实战拆解滑动窗口问题虽然变化多端但根据窗口长度是否固定、收缩条件是否明确可以归纳为几种经典模式。理解这些模式相当于掌握了解题的“公式”。2.1 套路一固定长度窗口——最直接的“尺子”这是最简单的一种。窗口大小k是预先给定的我们的任务就是让这个固定长度的窗口从数组或字符串的起始位置滑动到末尾并在每个位置计算窗口内的某个统计量如和、最大值、字符频率等。经典例题给定一个整数数组nums和一个整数k找出滑动窗口大小为k时窗口内元素的最大值。暴力法的思维陷阱新手可能会对每个窗口都重新遍历其中的k个元素找最大值时间复杂度为O(n*k)。当n和k都很大时这无法接受。滑动窗口优化思路关键在于当窗口滑动时只有两个元素发生变化离开窗口的左端元素和进入窗口的右端元素。我们需要一个数据结构能快速获取当前窗口的最大值并且在元素离开窗口时能高效地将其移除。双端队列deque是完美选择。Python实现与逐行解析from collections import deque def max_sliding_window(nums, k): 使用单调递减队列维护窗口最大值。 队列中存储的是元素的索引且对应元素值从队首到队尾递减。 if not nums or k 0: return [] result [] window deque() # 存储的是索引 for i, num in enumerate(nums): # 1. 维护队列的单调递减性如果当前元素大于队尾元素则不断弹出队尾 while window and nums[window[-1]] num: window.pop() # 将当前元素索引加入队尾 window.append(i) # 2. 移除已经滑出窗口的队首元素索引 if window[0] i - k: window.popleft() # 3. 当窗口长度达到k时开始记录结果队首元素即为当前窗口最大值索引 if i k - 1: result.append(nums[window[0]]) return result # 测试 nums [1, 3, -1, -3, 5, 3, 6, 7] k 3 print(max_sliding_window(nums, k)) # 输出: [3, 3, 5, 5, 6, 7]关键操作解析while window and nums[window[-1]] num: window.pop()这保证了队列是“单调递减”的。任何比当前新元素num小的旧元素都不可能再成为后续窗口的最大值因为num比它们大且比它们更晚离开窗口所以可以直接淘汰。if window[0] i - k: window.popleft()检查队首当前最大值的索引是否已经不在当前窗口范围内即索引小于等于i-k如果是则弹出。这是保证窗口范围正确的关键。if i k - 1:当右指针i移动到索引k-1时窗口第一次成型此后每次循环都可以记录一个结果。实操心得固定窗口的“前k项初始化”技巧对于固定窗口还有一种常见的写法是先用一个循环初始化第一个窗口的状态然后再开始滑动。例如先计算前k个元素的和或频率。这种写法逻辑更清晰尤其适用于窗口状态比较复杂如需要维护哈希表计数的情况。上面的单调队列写法更精妙但理解门槛稍高。根据问题复杂度选择最清晰的实现方式比追求“一行代码”更重要。2.2 套路二可变长度窗口求最长/最大——尽量扩张必要时收缩这是面试中最常见的一类。题目通常要求找到一个满足某些条件的最长子数组或子串。窗口从0开始我们总是尝试向右移动右指针r来扩大窗口以期找到更长的解。同时我们需要一个条件来判断当前窗口是否“合法”。当窗口变得“不合法”时我们就移动左指针l来收缩窗口直到它重新变得“合法”。经典例题给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。思维过程目标最长的不重复子串。策略右指针r探索新字符扩大窗口。用一个集合set或字典记录字符最新索引来快速判断字符是否重复。收缩条件当r指向的字符已经在当前窗口中出现过即发生重复窗口变得“不合法”。此时必须移动左指针l将重复字符及其之前的字符移出窗口直到重复被消除。Python实现使用集合def length_of_longest_substring(s: str) - int: char_set set() l 0 max_length 0 for r in range(len(s)): # 当前右指针字符 s[r] # 如果字符已在集合中说明重复需要收缩左边界 while s[r] in char_set: char_set.remove(s[l]) # 移除左指针字符 l 1 # 左指针右移 # 此时窗口 s[l:r1] 中无重复字符 char_set.add(s[r]) # 将当前字符加入集合 # 更新最大长度 max_length max(max_length, r - l 1) return max_length # 测试 print(length_of_longest_substring(abcabcbb)) # 输出: 3 (abc) print(length_of_longest_substring(bbbbb)) # 输出: 1 (b) print(length_of_longest_substring(pwwkew)) # 输出: 3 (wke)为什么用while而不是if这是新手常犯的错误。当s[r]重复时只收缩一次l 1可能不足以消除重复因为重复的字符可能不是窗口左端的那个。例如字符串“abca”当r指向最后一个‘a‘时重复字符是开头的‘a‘。用if只移动一次l到‘b‘集合里还有{‘b‘, ‘c‘, ‘a‘}仍然重复。必须用while循环持续收缩直到将第一个‘a‘移出集合。2.3 套路三可变长度窗口求最短/最小——找到合法窗口后积极收缩这类问题要求找到一个满足条件的最短子数组或子串。思路与求最长类似但策略更积极一旦找到一个“合法”窗口我们就不再盲目扩张右边界而是尝试收缩左边界看看能否在保持“合法”的前提下得到一个更短的窗口并记录这个更短的长度。经典例题给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和≥ target的长度最小的连续子数组并返回其长度。思维过程目标和 ≥ target 的最短子数组。策略右指针r探索扩大窗口并累加和window_sum。收缩时机一旦window_sum target我们就找到了一个合法窗口。此时立即尝试收缩左边界l在保持window_sum target的前提下尽可能右移l以得到更短的窗口。每次收缩后都更新最小长度。记录结果在收缩过程中记录得到的最小窗口长度。Python实现def min_sub_array_len(target: int, nums) - int: l 0 window_sum 0 min_len float(inf) # 初始化为无穷大 for r in range(len(nums)): window_sum nums[r] # 扩大窗口加入右指针元素 # 当窗口和满足条件时尝试收缩窗口 while window_sum target: # 更新最小长度 current_len r - l 1 min_len min(min_len, current_len) # 收缩窗口减去左指针元素左指针右移 window_sum - nums[l] l 1 # 如果min_len没有被更新过说明没有符合条件的子数组返回0 return min_len if min_len ! float(inf) else 0 # 测试 print(min_sub_array_len(7, [2,3,1,2,4,3])) # 输出: 2 ([4,3]) print(min_sub_array_len(11, [1,1,1,1,1,1,1,1])) # 输出: 0注意事项内外循环的对称性在“求最长”问题中内层while循环用于使窗口从不合法变为合法收缩直到合法。在“求最短”问题中内层while循环用于使窗口从合法变为不合法收缩直到刚好不合法前一个状态就是最短合法窗口。理解这个对称性能帮你快速判断该用while还是if以及循环条件是什么。2.4 套路四计数型窗口与哈希表维护——频率才是关键很多滑动窗口问题其“合法性”条件不是简单的和或重复字符而是基于字符或数字的频率。例如“找到字符串中所有字母异位词”、“最小覆盖子串”。这类问题的核心是维护两个哈希表或频率数组一个记录目标need一个记录当前窗口window并维护一个变量来跟踪当前窗口中有多少字符已经满足了目标频率要求valid。经典例题给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。思维拆解目标定义异位词意味着子串和p的长度相同且各个字符的出现次数相同。数据结构need字典记录p中每个字符需要的次数。window字典记录当前窗口中属于p的字符的出现次数。valid变量记录当前窗口中有多少种字符的出现次数已经达到了need要求。窗口移动逻辑右扩r右移字符c进入窗口。如果c在need中则增加window[c]。如果window[c]等于need[c]则valid。左缩当窗口长度大于len(p)时需要收缩。l右移字符d离开窗口。如果d在need中则需要先检查window[d]是否等于need[d]是则valid--然后再减少window[d]。结果记录在每次右扩后检查当前窗口长度是否等于len(p)且valid是否等于need中字符的种类数。如果都满足则l就是一个合法起始索引。Python实现from collections import Counter, defaultdict def find_anagrams(s: str, p: str): need Counter(p) # 目标字符频率 window defaultdict(int) # 窗口字符频率 l, r 0, 0 valid 0 # 窗口中满足need条件的字符种类数 result [] while r len(s): c s[r] r 1 # 右指针移动 # 进行窗口内数据的一系列更新 if c in need: window[c] 1 if window[c] need[c]: valid 1 # 判断左侧窗口是否要收缩当前窗口长度 目标字符串长度时 while r - l len(p): # 当窗口符合条件时记录结果 if valid len(need): # 所有字符种类都满足要求 result.append(l) # 将要移出窗口的字符 d s[l] l 1 # 左指针移动 # 进行窗口内数据的一系列更新 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return result # 测试 print(find_anagrams(cbaebabacd, abc)) # 输出: [0, 6] print(find_anagrams(abab, ab)) # 输出: [0, 1, 2]为什么需要valid变量如果不使用valid每次判断窗口是否合法都需要遍历need字典比较window和need的每个计数是否相等时间复杂度为O(26)或O(128)字符集大小虽然常数级但不够优雅。使用valid变量我们可以在O(1)时间内判断窗口是否满足所有字符的频率要求这是典型的以空间换时间的优化思想也是滑动窗口结合哈希表的精髓所在。3. 滑动窗口的通用解题框架与调试技巧经过上面几种套路的分析我们可以提炼出一个适用于大多数滑动窗口问题的通用框架。掌握这个框架相当于有了一个可靠的解题模板。3.1 四步通用框架模板以下是一个用Python实现的、高度抽象的滑动窗口框架涵盖了可变窗口求最值问题的核心逻辑。def sliding_window_template(s, t): # 初始化窗口左右指针、结果变量、窗口状态容器如哈希表、和、计数器等 l, r 0, 0 result ... # 可能是长度、列表等 window_state ... # 如window_sum 0, window_dict {}, window_set set() # 外层循环移动右指针探索整个区间 while r len(s): # 1. 将s[r]加入窗口更新窗口状态 # 例如window_sum s[r], window_dict[s[r]] 1, window_set.add(s[r]) update_state_add(s[r]) # 2. 内层循环根据条件判断是否需要收缩左指针 # 条件可能是窗口状态不合法、窗口长度超标、找到了一个可行解需要优化等 while condition_to_shrink(window_state): # 3. 在收缩前可能需要基于当前窗口更新最终结果 # 例如更新最小/最大长度记录子串等 update_result_if_needed() # 4. 将s[l]移出窗口更新窗口状态左指针右移 update_state_remove(s[l]) l 1 # 右指针右移准备下一轮循环 r 1 return result框架使用要点condition_to_shrink这是区分不同问题的关键。对于“求最长”条件通常是“窗口不合法”对于“求最短”条件通常是“窗口合法”。update_result_if_needed更新结果的时机也很重要。有时在收缩循环内更新如求最短有时在收缩循环外更新如求最长且合法时。指针移动顺序框架中r和l的移动是交错进行的。通常是r先移动扩大窗口然后根据条件用while移动l收缩窗口。确保指针永不回退单调移动这是O(n)复杂度的保证。3.2 调试与思维验证技巧即使有了框架写出代码后也可能遇到各种边界错误。分享几个我常用的调试方法打印窗口状态法在循环关键位置打印l,r,window_state如哈希表、和等。while r len(s): # ... 更新状态 print(f”l{l}, r{r}, window{window_state}, valid{valid}“) while condition_to_shrink: # ... 更新结果和状态 print(f” Shrink: l{l}, new_window{window_state}“)通过观察打印日志可以清晰看到窗口是如何扩张和收缩的快速定位逻辑错误。小数据暴力对比法对于复杂的滑动窗口逻辑可以用最朴素的暴力算法双重循环枚举所有子串在小数据集如长度20上运行将结果与你优化后的滑动窗口算法结果进行对比。这是验证算法正确性的黄金标准。边界条件手动模拟法在脑子里或纸上手动模拟算法在极端情况下的运行。空输入s”“,target0等。无解情况数组全部元素和仍小于target。解在两端最小子数组就是整个数组最长子串就是整个字符串。重复元素处理在哈希表更新时valid的加减是否与window[c] need[c]的判断严格对应这是最容易出错的地方。复杂度自检问自己每个元素每个s[r]和s[l]被放入窗口和移出窗口的操作是常数时间吗每个元素是否最多被访问两次一次被r访问一次被l访问如果答案是肯定的那么你的算法时间复杂度就是O(n)。4. 从LeetCode经典题到实战变种掌握了核心套路和框架后我们可以挑战一些更复杂的变种问题它们往往是对基本套路的组合或条件升级。4.1 变种一带有“成本”约束的窗口例题给你一个二进制数组nums和一个整数k你需要将其中最多k个0翻转成1请返回仅包含1的最长子数组的长度。问题转化这不再是简单的“无重复”或“和大于某值”而是“窗口内最多允许有k个0”。我们可以把问题转化为寻找一个最长的子数组其中包含的0的个数不超过k个。滑动窗口思路窗口状态记录当前窗口中0的个数zero_count。右扩r右移如果nums[r] 0则zero_count 1。收缩条件当zero_count k时窗口不合法需要收缩。左缩移动l如果nums[l] 0则zero_count - 1直到zero_count k。更新结果在每次右扩后且收缩完成后窗口都是合法的此时用r - l更新最大长度。def longest_ones(nums, k): l 0 zero_count 0 max_len 0 for r in range(len(nums)): if nums[r] 0: zero_count 1 while zero_count k: # 不合法需要收缩 if nums[l] 0: zero_count - 1 l 1 # 此时窗口合法 max_len max(max_len, r - l 1) return max_len4.2 变种二多条件与数据结构维护例题给你一个字符串s请你找出至多包含两个不同字符的最长子串的长度。思路分析窗口合法性条件变成了“包含不同字符的个数”。我们需要一个数据结构来高效地维护窗口中字符的频率并能快速知道当前有多少个不同的字符。哈希表字典仍然是首选。滑动窗口实现def length_of_longest_substring_two_distinct(s: str) - int: from collections import defaultdict l 0 char_count defaultdict(int) max_len 0 for r in range(len(s)): # 右指针字符进入窗口 char_count[s[r]] 1 # 收缩条件窗口中不同字符数大于2 while len(char_count) 2: # 左指针字符移出窗口 char_count[s[l]] - 1 if char_count[s[l]] 0: # 如果某个字符计数为0则从字典中删除 del char_count[s[l]] l 1 # 更新最大长度 max_len max(max_len, r - l 1) return max_len关键点在收缩时不仅要将左指针字符的计数减1当计数减到0时必须将其从字典中删除这样才能保证len(char_count)准确反映窗口中真正存在的不同字符数。这是使用哈希表维护计数型窗口时的一个经典细节。4.3 避坑指南滑动窗口的常见“天坑”指针移动与状态更新的顺序是先移动指针还是先更新状态顺序错了整个逻辑就乱了。我的经验法则是“右扩先更新左缩先判断”。即右指针移动后立即更新窗口状态加入新元素在左指针移动前先基于当前状态判断是否需要收缩如果需要则先更新结果如果需要再更新状态移除旧元素最后移动指针。while与if的误用这是最大的思维误区。记住一个原则当你无法确定收缩一次就能使窗口重新满足条件时就用while。在“无重复字符最长子串”中收缩一次可能移不掉重复字符在“和大于target的最短子数组”中收缩一次后可能和仍然大于target。在这些情况下必须用while循环持续收缩。窗口长度计算窗口长度通常是r - l 1当r和l是闭区间索引时或r - l当r是开区间索引指向下一个待处理元素时。在通用框架中我习惯使用while r len(s)和s[r]此时r是当前元素索引窗口长度为r - l 1。保持一致即可。哈希表valid变量的维护在频率问题中valid的增减必须与window[c] need[c]和window[c] need[c] - 1这样的精确判断绑定。增加时是在window[c] need[c]之后减少时是在window[c] need[c]之时。顺序反了就会计数错误。初始化和边界对于求最小值的问题结果初始值通常设为float(‘inf’)对于求最大值设为0或float(‘-inf’)。循环结束后要检查结果是否被更新过并返回合理的默认值如0。滑动窗口算法之所以强大在于它将一个复杂的问题转化为了指针的单调移动和窗口状态的增量更新。理解其本质是“双指针”的进阶并熟练掌握固定窗口、可变窗口求最长/最短、计数窗口这几种模式再配合通用的思维框架和细致的调试你就能攻克面试中绝大多数与之相关的难题。真正的掌握来自于将模板内化后对具体问题条件的准确翻译和映射。多练习多总结你会在代码中感受到这种算法之美。
