LeetCode Hot 100子串题三大利器：滑动窗口、前缀和、单调队列

有一说一LeetCode Hot 100 里的子串题是很多人口中“背了模板还是不会写”的典型代表。子串这个概念看起来就是一段连续的字符或数字可真到了无重复字符的最长子串、最小覆盖子串、和为 K 的子数组、滑动窗口最大值这些题很多人一上手就懵不是因为题难而是不知道这些题其实共用同一套底层思路。这篇文章我就以 hot100 子串题为主线把滑动窗口、前缀和、单调队列三种解法全部拆开讲讲每道题的选型逻辑、核心代码、以及我刷题时踩过的坑。适合正在准备面试的读者也适合那些刷完题单但缺乏系统总结的人。1. 子串题的完整思路拆解1.1 先弄清“子串”和“子序列”的区别很多人刷题刷了很久对这两个概念还是模糊的。子串是连续的必须从一个位置一直延伸到另一个位置中间不能断子序列则允许跳过某些字符只要保持相对顺序就行。hot100 里的子串题全部依赖“连续”这个性质正是这个性质决定了我们能用双指针和滑动窗口做线性扫描。如果题目换成子序列DP 或回溯会成为主流思路解法方向完全不同。这个区分看起来基础实际上决定了做题方向。我见过不少人在一道题上耗了一两个小时最后发现题目根本不是子串题而是子序列题方法选错再怎么写都是浪费时间。1.2 hot100 里子串题的分布与考察逻辑我翻了一遍 hot100 的题单子串相关的题大概集中在这么几道无重复字符的最长子串、最小覆盖子串、找到字符串中所有字母异位词、和为 K 的子数组、滑动窗口最大值。题号分别是 3、76、438、560、239。这几道题出现在 hot100 不是巧合它们分别对应了子串题的几种核心解法滑动窗口配合哈希表、前缀和配合哈希表、单调队列。考察的不是单点死记而是同一套思路在不同场景下的变形能力。面试官很少让你默写模板但很喜欢把“找异位词”改成“找排列”把“和为 K”改成“和为 K 的倍数”本质没变包装换了而已。题号题目核心解法关键难点3无重复字符的最长子串滑动窗口 哈希集合收缩窗口的时机76最小覆盖子串滑动窗口 双哈希表valid 计数维护438找到字符串中所有字母异位词滑动窗口 字符计数固定窗口的收缩条件560和为 K 的子数组前缀和 哈希表存在负数时不能滑动239滑动窗口最大值单调队列队首下标过期处理1.3 三种核心策略怎么选子串题我总结了三种策略。第一种是滑动窗口适合“窗口内满足某种条件”的题目比如无重复字符、覆盖目标串、包含异位词这类题基本都能用一套 right 扩张、left 收缩的模板解决。第二种是前缀和加哈希表适合求“某个区间的和等于目标值”这一类题。第三种是单调队列适合求“窗口内最大值或最小值”。选型时先判断条件是否随窗口单调变化如果两个指针都能单向移动滑动窗口大概率是正解如果需要统计之前出现过的状态就要靠前缀和和哈希表。我自己在带人刷题时经常说一句话选对解法题就做对了一半。后面几章我会把这三种策略逐一见血地展开。2. 滑动窗口模板与核心细节2.1 窗口维护的四大要素滑动窗口看起来就是两个指针但真正要管好的细节有四个right 什么时候右移、窗口什么时候该收缩、收缩时哪些状态要回滚、答案在哪个时机更新。这四个要素理清楚了窗口题基本不会写错。我见过很多初学者把 left 和 right 混在一起处理结果收缩完忘记恢复哈希表的计数整个 valid 计数就乱了。正确做法是固定右指针扩张每走一步就检查当前窗口是否满足条件满足就让左指针收缩直到条件刚好不满足这个过程中顺便收集答案。以最小覆盖子串为例右指针每加进来一个字符如果是目标串需要的就把它加入窗口计数当窗口内已经包含目标串的所有字符并且每种字符的个数都达标时就尝试收缩左指针。收缩的时候如果移除的字符刚好让某个字符的计数低于需求valid 减一窗口回到不满足状态。这个 valid 计数技巧非常关键它把“窗口内字符是否全部达标”的复杂判断变成了 O(1) 的整数比较。为什么不用每次扫一遍两个哈希表因为每次收缩都重扫的话复杂度就是 O(n * 字符集大小)数据一长就废了。2.2 模板代码与参数设计我先给一套我实测很久的滑动窗口模板这个模板建议直接背下来然后根据题目改四个地方window 的数据结构、need 的初始化、收缩条件、答案收集逻辑。from collections import defaultdict def sliding_window(s: str, t: str): need defaultdict(int) for c in t: need[c] 1 window defaultdict(int) left right 0 valid 0 # 根据题目需要维护答案变量比如 start, length while right len(s): c s[right] right 1 # 1. 更新窗口数据 if c in need: window[c] 1 if window[c] need[c]: valid 1 # 2. 收缩窗口的时机具体条件因题而异 while shrink_condition(): # 3. 在这里收集答案比如记录最小窗口的起始位置 d s[left] left 1 # 4. 回滚窗口数据 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return answer这里你会发现整个过程比较的都是“出现次数”而不是“是否包含”。原因很简单窗口里可能有多个重复字符如果一个字符在目标串里需要 3 次而现在只出现了 2 次就不能算达标。所以 need 的 value 存的是次数而不是布尔值。很多人的 bug 就出在把 value 当成 True/False 用重复字符一多就直接翻车。2.3 两道经典题的细节对照无重复字符的最长子串和最小覆盖子串是滑动窗口最典型的两个方向。前者要求窗口里没有重复字符所以窗口数据用一个 set 就好不需要计数后者要求窗口覆盖目标串的所有字符还允许窗口里有多余字符所以需要两个哈希表加一个 valid 计数。无重复字符那题右指针每进入一个字符如果发现窗口里已经有它了就不断收缩左指针把旧的同字符移出去然后再把新字符加进来同时更新最大长度。这里有个细节我反复强调收缩的 while 里要先移除、再添加顺序反了会把刚加进去的字符又删掉答案变成 0。def length_of_longest_substring(s: str) - int: window set() left 0 ans 0 for right, c in enumerate(s): while c in window: window.remove(s[left]) left 1 window.add(c) ans max(ans, right - left 1) return ans最小覆盖子串则相反它要求把所有目标字符都覆盖。这道题的答案收集时机是在收缩阶段因为我们要找“满足条件的最小长度”。每当窗口满足条件就对比更新 start 和 length然后继续收缩左指针。两题放在一起对照本质完全一样右指针扩张窗口满足条件后左指针收缩区别只是“满足条件”的定义不同。理解了这一点字母异位词那题基本就是套模板的固定窗口版本。3. 实操过程与核心环节实现3.1 和为 K 的子数组前缀和加哈希表先从小暴力说起。要统计数组中连续子数组和为 K 的个数最直接的做法是枚举每个起点和终点双循环算出所有区间和复杂度 O(n^2)在 10^5 级别的数据量下直接超时。为什么滑动窗口也不行因为数组里可能有负数窗口和不是单调变化的你没法确定右指针右移之后窗口和变大还是变小left 收缩的时机就无法判断。正解是前缀和。定义 prefix[i] 表示前 i 个元素的累加和那么从 j1 到 i 的区间和等于 prefix[i] - prefix[j]。我们要找的是有多少对满足 prefix[i] - prefix[j] K移项就是 prefix[j] prefix[i] - K。于是问题变成遍历到 i 时之前出现过多少个前缀和等于 prefix[i] - K。用一个哈希表记录每个前缀和出现的次数一趟遍历就能统计完。def subarray_sum(nums: list[int], k: int) - int: count_map {0: 1} prefix 0 ans 0 for num in nums: prefix num ans count_map.get(prefix - k, 0) count_map[prefix] count_map.get(prefix, 0) 1 return ans这里有个新手特别容易漏的点count_map 的初始值要写{0: 1}而不是空字典。因为前缀和可以等于 0当区间从头开始时j 之前的那个位置就是起点前的位置。漏掉这个初始化会少统计“前缀和刚好等于 K”的情况。还有一点是先查表再更新当前前缀和否则会把当前这个位置当成 j 用出现自己减自己、区间长度为 0 的错误统计。这两行顺序我见过太多人写反了写反的代码在小数据上还很难测出来。3.2 滑动窗口最大值单调队列滑动窗口最大值这题窗口大小固定为 k要求输出每个窗口内的最大值。有人第一反应是每个窗口扫一遍复杂度 O(nk)在 k 接近 n 的时候直接超时。这里的核心优化是维护一个单调递减的双端队列。队列里存的是下标队首到队尾对应的元素值严格递减。加入新元素时把队尾所有比它小的元素弹出因为它们存活时间短、值又不够大在后面的窗口里永远不可能成为最大值。同时还要把超出窗口范围的队首下标移出。from collections import deque def max_sliding_window(nums: list[int], k: int) - list[int]: q deque() ans [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: ans.append(nums[q[0]]) return ans注意弹出条件用的是而不是。用的意思是如果新元素和队尾元素相等新来的下标留在队里因为它的位置更靠后在窗口滑动后存活时间更长。这属于经验之谈很多题解不会专门讲这一行但实际写错之后在边界数据上会出现“窗口刚滑走一个最大值结果队列里存的还是它的旧下标”这种问题。3.3 从读题到 AC 的完整决策流程我把这几类题的决策流程整理成一套固定套路。先看目标是不是“连续片段”是就进入子串题范畴接着看统计的是“存在性”“区间和”还是“最值”。存在性优先滑动窗口区间和优先前缀和加哈希表最值优先单调队列。最后再看有没有负数、窗口是否固定、是否需要返回所有位置等附加条件用来修正模板。这套流程我每次带新人刷题都在用基本能覆盖 hot100 里 90% 的子串题。网上关于这几道题的题解非常多灵茶山艾府的每日题解我也一直在跟但光看别人的题解和自己动手写完全是两码事看完一定要关掉题解自己敲一遍。4. 常见问题与排查技巧实录4.1 边界条件总踩坑子串题的边界条件是重灾区我每次面试前都会把这些坑过一遍。空输入是最常见的s 是空串时滑动窗口模板虽然能跑但如果你在循环外直接用 s[0] 就会越界。最小覆盖子串的 length 初始值必须设成 float(inf)否则你没法判断“不存在覆盖串”的情况一上来初始化为 0最后判断永远以为找到了答案。和为 K 那题数组里存在负数时不能提前 break也不能用 left 收缩来优化必须完整扫描整个数组就因为这个很多面试者把滑动窗口硬套上去结果样例对了、大数据超时。问题现象根本原因修复方式最小覆盖子串返回空串length 初始化为 0初始化为 float(inf)最后判断和为 K 的结果偏少count_map 未初始化 {0: 1}提前写入 0 的前缀和窗口最大值结果错乱弹出条件用了 改成 保证下标新鲜valid 计数不准收缩时移除了多余字符却减了 valid只在 window[d] need[d] 时减4.2 性能优化与超时排查子串题的超时大多是两种原因一是用了 O(n^2) 的暴力枚举二是循环里调用了高开销操作。比如在循环里用 str.count 或 list 的 count 来判断字符出现次数这个操作本身是 O(n) 的套在双循环里复杂度直接爆炸。另外Python 的字符串切片会创建新字符串如果你在收集答案时频繁s[left:right]数据一大也会拖慢整体速度更稳的做法是用 start 和 length 记录位置最后再一次切片。哈希表的使用上也有些细节。用 defaultdict 确实方便但要注意遍历 Counter 时不能直接遍历字典本身再同时修改要先取出 items 或 keys。会不会出现内存问题其实子串题里哈希表存的是字符集大小最多几十个字母内存压力不大真正压力大的是前缀和那题如果用数组而不是哈希表去存前缀和出现次数当数字范围很大时根本开不出来所以哈希表是必须的。4.3 记忆模板时的三个误区第一只背代码不背“可改位置”。模板的价值在于四个可变点而不是那几行固定代码。第二不理解收缩时机。无重复字符题目里收缩是为了去重最小覆盖子串里收缩是为了找更小答案字母异位词里收缩是因为窗口长度已经等于目标串长度三种收缩时机完全不同混为一谈必然出错。第三忽视初始化和答案收集时机。count_map 的初始值、valid 的初始值、答案是在扩张后收集还是在收缩中收集这些细节才是区分“背过模板”和“真正会做”的关键。我自己练题时的习惯是每刷完一道子串题就把它改写成一个变形版本。比如把最小覆盖子串改成字符串排列那题把长度为固定的窗口把无重复字符的最长子串改成最多允许两个重复字符的版本。改一遍之后你对模板的理解会深很多面试官怎么换包装你都能接住。hot100 的子串题量不算大但每一道都值得反复咀嚼这套东西吃透了后面做任何窗口类的题目都会顺手很多。