滑动窗口算法详解：从原理到实战，攻克LeetCode高频面试题

1. 从一道高频面试题说起为什么滑动窗口是解题利器如果你刷过LeetCode或者准备过技术面试大概率遇到过这样一类问题给你一个字符串或者数组让你找出其中“不重复字符的最长子串”、“和大于等于目标值的最短子数组”或者“包含所有指定字符的最小子串”。我第一次遇到这类问题时第一反应往往是暴力破解——用两层循环枚举所有可能的子串或子数组然后逐一检查条件。比如找字符串中无重复字符的最长子串最直接的思路就是从索引i开始到索引j结束检查S[i:j1]里有没有重复字符。这个算法的时间复杂度是O(n²)对于长度上千的字符串计算起来就有点吃力了。后来我系统性地学习了滑动窗口Sliding Window算法才发现这类问题有一个通用的、优雅的优化思路。它的核心思想并不复杂维护一个窗口通常由两个指针left和right定义通过移动right指针来扩展窗口满足条件后再移动left指针来收缩窗口在此过程中不断更新答案。这个技巧能将许多原本需要O(n²)时间的问题优化到O(n)因为它避免了重复计算每个元素最多被left和right指针各访问一次。今天我们就用Python来彻底拆解滑动窗口算法。我会从最基本的固定窗口大小问题讲起然后深入到更常见的可变大小窗口并结合多个经典例题把窗口扩张与收缩的时机、数据结构的选择、边界条件的处理这些容易踩坑的细节都捋清楚。无论你是刚开始接触算法还是想巩固这一高频考点这篇文章都能给你提供可直接“抄作业”的模板和思路。2. 滑动窗口的两种基本形态固定窗口与可变窗口滑动窗口算法主要解决的是数组/字符串的子区间问题。根据窗口在滑动过程中大小是否变化可以分为两大类。理解这两种形态是掌握所有滑动窗口题目的基础。2.1 固定大小的滑动窗口这是最简单的一种。窗口的大小k在初始化时就确定了在滑动过程中保持不变。解题模板非常固定初始化先处理第一个窗口从索引0到k-1的数据计算出初始结果如和、最大值等。滑动将窗口向右移动一格。这意味着有一个旧元素窗口最左端离开窗口一个新元素窗口右端下一个进入窗口。更新根据离开和进入的元素高效地更新窗口状态如窗口和而无需重新遍历整个窗口。重复步骤2和3直到窗口滑动到数组末尾。一个经典例子计算大小为k的子数组的最大平均值。给定数组nums [1, 12, -5, -6, 50, 3]k 4。暴力法是计算每个长度为4的子数组的和然后取平均值的最大值时间复杂度O(n*k)。用固定滑动窗口可以优化到O(n)。def find_max_average(nums, k): # 计算第一个窗口的和 window_sum sum(nums[:k]) max_sum window_sum # 开始滑动窗口 for i in range(k, len(nums)): # 窗口向右滑动一格减去离开的左端元素加上新进入的右端元素 window_sum window_sum - nums[i - k] nums[i] # 更新最大和 max_sum max(max_sum, window_sum) # 返回最大平均值 return max_sum / k # 测试 nums [1, 12, -5, -6, 50, 3] k 4 print(find_max_average(nums, k)) # 输出 12.75 (子数组 [12, -5, -6, 50] 的和是51)这里的核心技巧在滑动时我们不是用sum(nums[i-k1: i1])重新计算而是用window_sum - nums[i-k] nums[i]来更新。这利用了前缀和的思想将每次更新窗口状态的复杂度从O(k)降到了O(1)。这是固定窗口效率提升的关键。注意固定窗口问题有时会伪装一下。比如LeetCode 567题“字符串的排列”判断s2是否包含s1的排列。这本质上是在s2上维护一个长度固定为len(s1)的窗口然后检查这个窗口的字符计数是否和s1的字符计数完全一致。解题时我们需要一个长度为26的数组假设只有小写字母来记录频率滑动窗口时更新这个频率数组即可。2.2 可变大小的滑动窗口双指针型这是面试中最常见、也最灵活的一类。窗口的大小不固定left和right指针的移动策略由题目条件动态决定。通常用于求解“最短”、“最长”、“子串”等问题。通用解题框架如下def sliding_window_template(s): left 0 # 通常用一个字典或集合来记录窗口内的状态如字符出现次数 window {} # 记录最终答案如最大长度、最小长度等 result 0 for right in range(len(s)): # 1. 将s[right]加入窗口更新窗口状态 char s[right] window[char] window.get(char, 0) 1 # 2. 判断当前窗口是否满足了某种“需要收缩”的条件 while (window_needs_shrink): # 3. 在收缩窗口前可能需要基于当前窗口更新最终答案 # 例如更新最长子串长度result max(result, right - left 1) # 4. 将s[left]移出窗口更新窗口状态 left_char s[left] window[left_char] - 1 if window[left_char] 0: del window[left_char] # 可选保持字典清洁 left 1 # 左指针右移收缩窗口 # 5. 在窗口满足条件时或收缩后满足条件时更新答案 # 有时答案更新在while循环内部有时在外部需根据题目判断 result max(result, right - left 1) return result这个框架的灵魂在于第2步的while循环条件。这个条件决定了何时收缩窗口。对于“最长”类问题如无重复字符的最长子串我们是在窗口不满足条件时出现重复字符才收缩对于“最短”类问题如和大于等于目标的最短子数组我们是在窗口满足条件时和已经目标才收缩以尝试找到更短的。3. 攻克高频题型从“最长”到“最短”的实战拆解理解了基本形态我们来看几个必须掌握的经典题型。我会把代码、思路和容易出错的细节都讲透。3.1 最长无重复字符子串LeetCode 3这是可变窗口的入门必做题。题目要求找到给定字符串中不含有重复字符的最长子串的长度。思路分析窗口定义[left, right]闭区间内的子串无重复字符。扩张时机right指针每次循环向右移动一位将新字符纳入窗口。收缩时机当新字符char加入后导致窗口内该字符的计数大于1即出现重复此时需要收缩left指针直到重复字符被移出窗口其计数降回1。更新答案时机在每次扩张后、且尚未触发收缩时或者收缩完成后此时的窗口是满足条件的可以计算其长度right - left 1并更新最大值。def length_of_longest_substring(s: str) - int: from collections import defaultdict window defaultdict(int) # 记录窗口内各字符的出现次数 left 0 max_len 0 for right in range(len(s)): char s[right] window[char] 1 # 右指针字符进入窗口 # 关键当新字符导致重复计数1需要收缩左边界 while window[char] 1: left_char s[left] window[left_char] - 1 left 1 # 左指针右移 # 此时窗口[left, right]内无重复字符更新答案 max_len max(max_len, right - left 1) return max_len # 测试 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这里必须用while。因为新加入的字符char可能和窗口里多个字符重复吗不会它只可能和自己重复计数1。但收缩left时一次移动可能只移除了另一个重复字符而char本身还在窗口里计数依然为2所以需要持续收缩直到window[char] 1。用if只能收缩一次可能清理不干净。数据结构选择使用defaultdict(int)比普通字典写起来简洁。也有人用set但set无法处理计数当left移动时你无法知道移出的字符在窗口内是否还有副本所以用计数字典是更通用的做法。边界条件空字符串输入应返回0。上述代码中for right in range(len(s)):在s为空时不会进入循环max_len初始为0最终返回0正确。3.2 最小覆盖子串LeetCode 76这是滑动窗口的“困难”经典题要求你在字符串s中找出涵盖字符串t所有字符的最短子串。如果不存在返回空字符串。思路分析核心转化问题转化为在s上找到一个窗口使得窗口内包含t的所有字符包括数量。例如tAABC则窗口必须至少包含2个A1个B1个C。数据结构需要两个计数字典need记录t中每个字符需要的数量window记录当前窗口中相应字符的数量。关键变量引入valid变量表示当前窗口中已经满足need要求的字符种类数。当valid len(need)时说明窗口已完全覆盖t。扩张与收缩right右移扩张窗口更新window。如果当前字符char在need中且window[char]达到了need[char]则valid。当valid len(need)窗口满足条件开始收缩以寻找更短的可能。移动left指针在缩小窗口前更新答案记录起始位置和长度并更新window和valid。def min_window(s: str, t: str) - str: from collections import defaultdict need, window defaultdict(int), defaultdict(int) for c in t: need[c] 1 left 0 valid 0 # 满足need条件的字符种类数 # 记录最小覆盖子串的起始索引和长度 start, min_len 0, float(inf) for right in range(len(s)): c s[right] # 右移窗口 if c in need: window[c] 1 if window[c] need[c]: valid 1 # 判断左侧窗口是否要收缩 while valid len(need): # 更新最小覆盖子串 if right - left 1 min_len: start left min_len right - left 1 # 将要移出窗口的字符 d s[left] left 1 # 更新窗口数据 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return if min_len float(inf) else s[start:startmin_len] # 测试 print(min_window(ADOBECODEBANC, ABC)) # 输出 BANC print(min_window(a, aa)) # 输出 为什么这是难点关键在于valid的理解。我们并不要求窗口内t中每个字符的数量完全等于need而是至少等于。valid记录的是“已经达标”的字符种类。当window[c]从need[c]-1增加到need[c]时c这个种类才达标valid1。当window[d]从need[d]减少到need[d]-1时d这个种类不再达标valid-1。这个设计完美地避免了我们去比较两个字典的所有键值对将判断窗口是否满足条件的复杂度降到了O(1)。3.3 长度最小的子数组LeetCode 209这是可变窗口处理数组求和问题的典型。给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和≥ target的长度最小的连续子数组并返回其长度。思路分析数组元素都是正数这是一个非常重要的条件它保证了窗口和window_sum随着right右移而单调递增随着left右移而单调递减。这个性质是使用滑动窗口的前提之一如果数组包含负数窗口和变化不确定滑动窗口可能失效需要考虑前缀和二分查找。扩张与收缩移动right累加window_sum。当window_sum target时说明当前窗口满足条件。此时我们尝试收缩left指针以找到更短的子数组同时更新最小长度。收缩的条件是window_sum target并且要持续收缩直到window_sum target因为可能收缩多次后依然满足条件。def min_sub_array_len(target: int, nums: list[int]) - int: left 0 window_sum 0 min_len float(inf) for right in range(len(nums)): window_sum nums[right] # 扩张窗口 # 当窗口和满足条件时尝试收缩窗口寻找更优解 while window_sum target: # 更新答案 min_len min(min_len, right - left 1) # 收缩窗口 window_sum - nums[left] left 1 return 0 if min_len float(inf) else min_len # 测试 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循环是当窗口满足条件和target时执行目的是在满足条件的前提下尝试找到更短的窗口。这是两类问题最根本的区别务必理解透彻。4. 滑动窗口的进阶技巧与复杂场景应对掌握了基本题型我们来看看一些需要更多技巧的场景。这些地方往往是区分熟练度的关键。4.1 需要记录索引的窗口字符与最新位置映射有些题目不仅需要知道字符是否存在还需要知道它最近一次出现的位置。例如另一种解决“最长无重复子串”的思路是使用字典记录每个字符最后一次出现的索引。思路当right指针向右扫描时如果当前字符s[right]之前出现过在字典中并且其上次出现的位置last_seen[char]大于等于当前窗口的左边界left说明这个重复字符就在当前窗口内我们必须将left指针移动到last_seen[char] 1直接跳过这个重复字符。否则如果上次出现的位置在left左边说明它不在当前窗口内不影响。def length_of_longest_substring_v2(s: str) - int: last_seen {} # 字符 - 其最后出现的位置索引 left 0 max_len 0 for right, char in enumerate(s): # 如果字符出现过且在当前窗口内更新左边界 if char in last_seen and last_seen[char] left: left last_seen[char] 1 # 更新字符的最后出现位置 last_seen[char] right # 计算当前窗口长度 max_len max(max_len, right - left 1) return max_len这种方法将空间复杂度优化到了字符集的大小并且left的移动是跳跃式的而不是一步步while循环在某些情况下更高效。它体现了滑动窗口思想的灵活性窗口的左边界可以直接根据问题性质“跳跃”更新。4.2 计数不再是0/1至多包含K个不同字符的最长子串LeetCode 340这是对基础无重复字符问题的一个扩展。给定一个字符串s和一个整数k找到s中最多包含k个不同字符的最长子串的长度。思路分析窗口状态我们需要知道窗口内有多少种不同的字符。当不同字符种类数len(window)大于k时窗口需要收缩。收缩策略移动left指针减少对应字符的计数。当某个字符的计数减到0时从window字典中删除该键这样len(window)就会减少。def length_of_longest_substring_k_distinct(s: str, k: int) - int: from collections import defaultdict window defaultdict(int) left 0 max_len 0 for right in range(len(s)): char s[right] window[char] 1 # 当窗口内不同字符数超过k时收缩左边界 while len(window) k: left_char s[left] window[left_char] - 1 if window[left_char] 0: del window[left_char] # 关键当计数为0时删除键len(window)才会变化 left 1 # 更新答案 max_len max(max_len, right - left 1) return max_len # 测试 print(length_of_longest_substring_k_distinct(eceba, 2)) # 输出 3 (ece) print(length_of_longest_substring_k_distinct(aa, 1)) # 输出 2 (aa)关键细节在收缩窗口的while循环里if window[left_char] 0: del window[left_char]这行代码至关重要。如果只是将计数减到0而不删除键len(window)不会改变while循环的条件len(window) k将永远为真导致死循环。这个细节在需要维护“种类数”的滑动窗口问题中非常常见。4.3 窗口内状态的维护使用Counter与defaultdictPython的collections模块是滑动窗口算法的好帮手。defaultdict(int)如上文广泛使用的初始化字典时所有键默认值为0方便进行计数操作window[char] 1无需先判断键是否存在。Counter来自collections可以快速生成频率字典。例如need Counter(t)。但注意Counter对象在减法操作时有特殊行为counter1 - counter2会减去计数并移除计数0的项在滑动窗口场景中手动更新window字典通常更直观可控。我个人更倾向于使用defaultdict(int)因为逻辑更清晰对窗口状态的增减完全由代码控制不容易出错。5. 滑动窗口算法的边界条件与调试技巧即使理解了算法框架实际编码时依然可能被边界条件困住。这里分享几个我调试时的心得。5.1 指针初始值与循环范围left指针通常初始化为0。right指针的循环我习惯用for right in range(len(s)):这样right直接就是索引清晰明了。也有人用while right len(s):然后手动right 1但for循环更简洁。窗口长度计算right - left 1。因为right和left都是闭区间索引。更新答案的位置这是最容易出错的地方。务必想清楚当前窗口在什么状态下是符合题目要求的是在while循环收缩之前还是收缩之后还是for循环的末尾多拿几个简单例子在纸上模拟一下指针移动和状态更新就能找准位置。5.2 复杂条件判断的简化对于“最小覆盖子串”这类复杂条件引入valid这样的辅助变量是简化逻辑的关键。不要试图在每次循环中都去完整比较need和window两个字典那样时间复杂度就上去了。将“窗口是否满足条件”这个判断转化为对几个简单计数器状态的判断是写出高效滑动窗口代码的核心技巧。5.3 从暴力法到滑动窗口的思考路径如果你拿到一个新问题不确定是否能用滑动窗口可以这样思考问题是否涉及连续子数组或子串滑动窗口只适用于连续区间问题。暴力解法是什么通常是两层循环枚举所有子区间复杂度O(n²)。窗口的扩张right右移是否具有单调性即加入新元素后窗口的某个状态如和、不同字符数是单调变化的通常因为题目限制如元素为正数。当窗口状态满足/不满足某个条件时能否通过移动left来调整而不是重置整个窗口如果能就可以尝试滑动窗口来优化。例如在“和大于等于目标的最短子数组”中因为元素为正窗口和随right右移单调增。当窗口和target时我们移动left来减小和尝试找更短的窗口。这个“移动left”而不是“重置left到right1”的操作就是滑动窗口节省时间的本质。滑动窗口算法之所以高效正是因为它巧妙地利用了问题的性质避免了重复计算。它不是一种死记硬背的模板而是一种基于双指针、利用单调性进行优化的思想。多练习多思考每种题型中指针移动的原因和时机你就能在面对新的变种题目时快速识别并设计出正确的窗口维护策略。