LeetCode 热题 100 题解（3）：滑动窗口

LeetCode 热题 100 题解3滑动窗口一、什么是滑动窗口在上一篇博客中我们探讨了双指针技巧。这次要介绍的滑动窗口算法实际上是双指针思想的一种特殊应用。我们可以将其形象地比作在一维数组上移动的观察窗口通过左右两个指针来界定窗口的边界。与普通双指针不同的是这个窗口始终保持单向向右移动的特性右指针负责扩展窗口范围纳入新元素而左指针则负责收缩窗口排除不必要的数据。为什么要设计这种算法呢在数组与字符串处理中我们常遇到这样的需求寻找满足特定条件的连续区间子数组或子串并计算其最大/最小长度、数量或区间极值。最直观的解法是暴力枚举所有可能的左右边界通过双重循环逐一检查每个区间。然而这种方法存在明显缺陷相邻区间包含大量重复元素每次重新计算区间属性会导致严重的效率浪费时间复杂度高达 O(n²)稍大数据量就会超时。滑动窗口算法则能高效解决这个问题。通过动态维护窗口内的有效信息每个元素最多被处理两次进入和离开窗口从而将整体时间复杂度优化至线性 O(n)。滑动窗口算法的正确运行依赖于一个关键前提——单调性。所谓单调性指的是窗口状态的变化遵循单一方向趋势不会出现反复波动。这意味着当窗口满足或违反特定条件时通过扩展或收缩窗口所产生的结果都是可预测的。我们结合具体例子来分析。比如要求区间内至多 k 种不同字符求最长合法区间。假设窗口 [L, R] 是合法窗口。那么它内部所有更窄的窗口 [Lx, R] 依然合法。收缩只会更容易合法而向外扩张更容易变得不合法。再比如要求窗口包含目标所有字符求最短合法区间假设窗口 [L, R] 合法。那么向外拓展得到的 [L, R1] 依旧合法。 窗口拉大不会丢失合法性向内收缩才可能变成非法。最后再看一个没有单调性的反面例子数组有正有负寻找和等于 k 的子数组。比如 nums[2,-1,3], k3窗口和没有单调趋势——不管向外拓展还是向内收缩和可能变大、也可能变小此时滑动窗口就不再适用。因此遇到连续区间问题时需要先判断区间是否具有单调性不可盲目套用滑动窗口。根据窗口长度是否固定滑动窗口可分为两类一种是长度不变的定长滑动窗口每次移动固定步长另一种是长度可变的动态滑动窗口能根据条件自动调整窗口大小这也是算法考试和面试中的重点考察内容。在实际应用中不同题目需要维护的窗口信息各异常见的有字符出现频率区间元素和区间最大值元素种类数量这些需求衍生出多种实现方式包括普通计数滑动窗口结合前缀和的滑动窗口使用单调队列的滑动窗口初学者常犯的错误是死记硬背代码模板但掌握滑动窗口算法的关键在于理解三个核心问题如何定义合法窗口的条件何时扩展右边界何时收缩左边界窗口元素变化时如何同步更新统计信息接下来我们将通过两道典型例题逐步剖析不同场景下的滑动窗口实现方法并总结各类题型的共性和易错点。二、例题1.无重复字符的最长子串找符合要求的连续区间是滑窗的典型应用我们来看此题能否使用滑动窗口。合法窗口的条件是窗口内的所有字符必须不重复。观察单调性规律如果窗口 [left, right] 满足无重复那么任意向内收缩得到的 [leftx, right] 一定也合法当窗口向右扩张时有可能引入重复字符使窗口变为非法。这种单向稳定的规律性满足了滑动窗口算法所需的单调性前提确保了左右指针只需单向右移。如此我们再来规划算法流程右指针 right持续向右移动不断把新字符纳入窗口尝试扩大候选区间每当新加入字符造成窗口出现重复窗口非法持续右移 left不断剔除窗口最左侧字符直到窗口重新恢复 “无重复” 的合法状态窗口处于合法状态时实时计算当前窗口长度持续更新全局最长长度。classSolution(object):deflengthOfLongestSubstring(self,s): :type s: str :rtype: int char_setset()left0lengthlen(s)max_len0forrightinrange(length):# 存在重复不断收缩左边界whiles[right]inchar_set:char_set.remove(s[left])left1char_set.add(s[right])max_lenmax(max_len,right-left1)returnmax_len当然我们没有必要让 left 一格一格地走动而是用哈希表记录字符最新下标让 left 直接跳到重复字符下一位以此对左指针跳跃做一定优化。classSolution(object):deflengthOfLongestSubstring(self,s):last_posdict()max_len0left0forright,cinenumerate(s):# 字符出现过并且位置left说明在当前窗口内重复ifcinlast_posandlast_pos[c]left:leftlast_pos[c]1last_pos[c]right max_lenmax(max_len,right-left1)returnmax_len这种算法每个字符最多入集合、出集合一次时间复杂度 O (n)。2.找到字符串中所有字母异位词在讲解哈希表时我们曾以字母异位词为例介绍了排序法和计数法两种解法其中计数法具有更优的时间复杂度。基于此我们可以采用固定窗口法将窗口大小设为模式串p的长度通过滑动窗口统计字符出现频次。具体实现步骤如下1.创建两个频次数组p_count 数组记录模式串p中各字符的所需数量s_count 数组统计当前滑动窗口内的字符分布情况2.初始化第一个完整窗口计算初始字符频次3.滑动窗口操作右移窗口时移除左侧滑出边界的字符并更新 s_count 数组纳入右侧新进入窗口的字符同步更新 s_count 数组4.每当形成完整窗口时检查 s_count 与 p_count 是否完全匹配若匹配则记录当前窗口的起始位置。classSolution(object):deffindAnagrams(self,s,p): :type s: str :type p: str :rtype: List[int] s_lenlen(s)p_lenlen(p)res[]# 边界s比p短不可能存在异位词ifs_lenp_len:returnres# 计数数组对应26个小写英文字母s_count[0]*26p_count[0]*26# 初始化统计p的字符频次同时统计s第一个窗口的频次foriinrange(p_len):p_count[ord(p[i])-ord(a)]1s_count[ord(s[i])-ord(a)]1foriinrange(s_len-p_len1):# 判断当前窗口是否匹配ifs_countp_count:res.append(i)ifis_len-p_len:# 移出窗口左侧的字符s_count[ord(s[i])-ord(a)]-1# 加入窗口右侧的新字符s_count[ord(s[ip_len])-ord(a)]1returnres三、总结滑动窗口是双指针思想的延伸专门用于解决连续子数组或子串问题。其核心原理在于区间状态的单调性窗口扩展或收缩导致的合法性变化具有单向趋势确保左右指针只向右移动从而将复杂度从暴力解法的 O(n2) 优化至线性的 O(n)。根据窗口长度是否固定可分为两类定长滑动窗口特点窗口长度固定每次整体右移一格 流程 初始化时填满窗口 每次移动时移除最左元素并纳入新右元素 持续维护窗口统计信息适用场景目标区间长度已知典型问题有字符串字母异位词、滑动窗口最大值可变长度滑动窗口根据目标不同分为两种模式最长合法区间右指针持续扩展直到非法再收缩左边界。例如无重复字符的最长子串最短合法区间右指针扩展至合法后左指针压缩寻找最小值。例如最小覆盖子串在具体实现中常用三种方式维护窗口信息对于普通字符统计通常采用频率数组基于桶计数思想当需要获取区间最值时使用单调队列若需记录元素位置信息则选择哈希字典。一般解题步骤确认问题是否涉及连续区间验证单调性并判断窗口类型定长/可变定义合法窗口条件确定窗口扩展/收缩的触发条件设计数据结构及更新逻辑在适当时机更新最终答案