LeetCode刷题保姆级攻略：用滑动窗口秒杀「无重复字符的最长子串」和「最小覆盖子串」

LeetCode滑动窗口算法精讲从暴力解法到最优解的思维跃迁滑动窗口算法是解决字符串和数组子序列问题的利器尤其适合处理最长子串、最小覆盖子串这类经典问题。很多开发者在初次接触这类题目时往往会陷入暴力解法的思维定式导致代码效率低下。本文将带你突破这一瓶颈掌握滑动窗口的核心思想与实战技巧。1. 滑动窗口的本质与适用场景滑动窗口算法本质上是一种双指针技巧的高级应用它通过维护一个动态变化的窗口来避免不必要的重复计算。想象你在观察一个不断滑动的窗户透过这个窗户你只能看到数组或字符串的一部分——这正是算法名称的由来。适用滑动窗口的问题通常具有以下特征问题涉及数组/字符串的连续子序列需要寻找满足特定条件的最大/最小窗口暴力解法通常需要O(n²)或更高时间复杂度例如在「无重复字符的最长子串」问题中我们需要找到一个字符串中不包含重复字符的最长连续子串。暴力解法会检查所有可能的子串而滑动窗口可以将时间复杂度优化到O(n)。提示当题目中出现子串、子数组、连续等关键词时优先考虑滑动窗口解法。2. 滑动窗口的通用框架与实现所有滑动窗口问题都遵循相似的基本框架。下面是一个Python实现的通用模板def sliding_window(s: str) - int: left 0 # 窗口左边界 result 0 # 存储最终结果 window {} # 用于记录窗口内元素的状态 for right in range(len(s)): # 右指针遍历整个字符串 # 1. 将当前字符加入窗口 char s[right] window[char] window.get(char, 0) 1 # 2. 当窗口不满足条件时收缩左边界 while window_needs_shrink(window): left_char s[left] window[left_char] - 1 if window[left_char] 0: del window[left_char] left 1 # 左指针右移 # 3. 更新结果 result max(result, right - left 1) return result这个模板包含了滑动窗口算法的三个关键步骤扩展窗口右指针移动将新元素纳入窗口收缩窗口当窗口不满足条件时左指针移动以缩小窗口更新结果在每次窗口满足条件时记录当前最优解实际应用时需要根据具体问题调整window_needs_shrink的判断条件窗口数据的存储方式哈希表、计数器等结果更新的逻辑3. 经典问题解析无重复字符的最长子串让我们用上述框架解决LeetCode第3题「无重复字符的最长子串」。题目要求找到给定字符串中不含有重复字符的最长子串的长度。3.1 问题分析输入字符串abcabcbb 预期输出3abc是最长无重复子串关键点需要检测窗口内是否有重复字符当出现重复时需要收缩窗口直到重复被消除记录过程中出现的最大窗口大小3.2 代码实现def lengthOfLongestSubstring(s: str) - int: left 0 max_len 0 char_index {} # 存储字符及其最后出现的位置 for right in range(len(s)): char s[right] # 如果字符已存在且位置在窗口内需要收缩窗口 if char in char_index and char_index[char] left: left char_index[char] 1 # 更新字符的最新位置 char_index[char] right # 计算当前窗口长度 max_len max(max_len, right - left 1) return max_len3.3 复杂度分析时间复杂度O(n)每个字符最多被访问两次右指针和左指针各一次空间复杂度O(min(m, n))其中m是字符集大小n是字符串长度优化点使用数组代替哈希表可以进一步优化常数时间特别是当字符集已知且较小时如仅包含ASCII字符。4. 进阶问题最小覆盖子串LeetCode第76题「最小覆盖子串」是滑动窗口的经典难题。题目要求在字符串s中找到包含字符串t所有字符的最小子串。4.1 问题分析输入s ADOBECODEBANC, t ABC 输出BANC关键点需要统计t中所有字符的出现次数窗口需要包含t的所有字符且次数不少于t中的次数需要在满足条件的窗口中寻找最小的那个4.2 代码实现from collections import defaultdict def minWindow(s: str, t: str) - str: if not s or not t or len(s) len(t): return # 初始化需求字典 need defaultdict(int) for c in t: need[c] 1 need_cnt len(t) # 总共需要的字符数 left 0 min_len float(inf) result for right in range(len(s)): char s[right] if char in need: if need[char] 0: need_cnt - 1 need[char] - 1 # 当窗口满足条件时 while need_cnt 0: # 更新最小窗口 if right - left 1 min_len: min_len right - left 1 result s[left:right1] # 尝试收缩左边界 left_char s[left] if left_char in need: need[left_char] 1 if need[left_char] 0: need_cnt 1 left 1 return result4.3 解题技巧使用计数器need_cnt跟踪还需要匹配的字符总数避免每次检查整个需求字典负值处理当窗口中有多余的所需字符时need字典中的值可以为负结果更新时机仅在need_cnt 0时考虑更新结果5. 滑动窗口的变体与优化滑动窗口算法在实际应用中存在多种变体掌握这些变体可以解决更复杂的问题。5.1 固定大小的滑动窗口有些问题的窗口大小是固定的如「找到字符串中所有字母异位词」LeetCode 438。这种情况下窗口的左右指针总是同步移动。def findAnagrams(s: str, p: str) - List[int]: if len(s) len(p): return [] p_count [0] * 26 s_count [0] * 26 result [] # 初始化p的字符计数 for c in p: p_count[ord(c) - ord(a)] 1 # 初始化滑动窗口 for i in range(len(p)): s_count[ord(s[i]) - ord(a)] 1 if s_count p_count: result.append(0) # 滑动窗口 for i in range(len(p), len(s)): # 移除左边界的字符 left_char s[i - len(p)] s_count[ord(left_char) - ord(a)] - 1 # 添加右边界的字符 right_char s[i] s_count[ord(right_char) - ord(a)] 1 if s_count p_count: result.append(i - len(p) 1) return result5.2 多指针滑动窗口对于更复杂的问题可能需要维护多个指针或状态。例如「水果成篮」LeetCode 904问题需要跟踪窗口中的两种不同类型。def totalFruit(fruits: List[int]) - int: basket {} left 0 max_fruits 0 for right in range(len(fruits)): fruit fruits[right] basket[fruit] basket.get(fruit, 0) 1 # 当篮子中有超过2种水果时 while len(basket) 2: left_fruit fruits[left] basket[left_fruit] - 1 if basket[left_fruit] 0: del basket[left_fruit] left 1 max_fruits max(max_fruits, right - left 1) return max_fruits5.3 前缀和与滑动窗口结合当问题涉及子数组和时可以结合前缀和技巧。例如「和至少为K的最短子数组」LeetCode 862需要使用单调队列优化滑动窗口。6. 常见错误与调试技巧即使掌握了滑动窗口的基本思想实际编码中仍会遇到各种问题。以下是几个常见错误及解决方法错误1窗口收缩条件不正确症状程序无法找到正确解或陷入无限循环。解决方法仔细分析问题条件确保收缩条件准确反映问题要求。可以手动模拟小例子验证。错误2结果更新时机不当症状程序能找到部分解但不是最优解。解决方法明确何时应该更新结果——通常在窗口满足条件时但有时需要在收缩过程中更新。错误3数据结构选择不当症状算法时间复杂度过高无法通过大规模测试。解决方法根据问题特点选择高效的数据结构如用数组代替哈希表处理有限字符集问题。调试技巧打印窗口状态在每次指针移动时打印窗口内容使用小测试用例手动验证算法是否正确边界条件检查空输入、所有元素相同等特殊情况# 调试示例在滑动窗口代码中添加打印语句 def debug_sliding_window(s): left 0 result 0 window set() for right in range(len(s)): char s[right] print(f\n右指针移动到 {right}, 字符 {char}) while char in window: print(f 重复字符 {char}, 左指针从 {left} 移动到 {left1}) window.remove(s[left]) left 1 window.add(char) print(f当前窗口: {window}, 长度: {right - left 1}) result max(result, right - left 1) return result7. 滑动窗口与其他算法的比较理解滑动窗口与其他相似算法的区别有助于在解题时选择最合适的工具。算法适用场景时间复杂度空间复杂度特点滑动窗口连续子序列问题O(n)O(k)双指针动态维护窗口动态规划子序列问题不要求连续O(n²)O(n)记忆化递归解决重叠子问题分治法可分割的复杂问题O(nlogn)O(logn)将问题分解为更小的子问题暴力枚举所有问题O(n²)或更高O(1)简单但效率低何时选择滑动窗口问题涉及数组/字符串的连续子序列需要优化暴力解法的时间复杂度可以定义明确的窗口条件满足/不满足滑动窗口的局限性不适用于非连续子序列问题对于某些复杂条件可能难以设计收缩条件需要额外的空间存储窗口状态在实际面试中我经常先考虑暴力解法然后分析是否有重叠计算可以通过滑动窗口优化。这种从简单到复杂的思考过程也更容易向面试官展示。