企业官网建设流程全解析

有一说一，LeetCode Hot 100 里的子串题，是很多人口中“背了模板还是不会写”的典型代表。子串这个概念看起来就是一段连续的字符或数字，可真到了无重复字符的最长子串、最小覆盖子串、和为 K 的子数组、滑动窗口最大值这些题，很多人一上手就懵，不是因为题难，而是不知道这些题其实共用同一套底层思路。这篇文章我就以 hot100 子串题为主线，把滑动窗口、前缀和、单调队列三种解法全部拆开，讲讲每道题的选型逻辑、核心代码、以及我刷题时踩过的坑。适合正在准备面试的读者，也适合那些刷完题单但缺乏系统总结的人。

1. 子串题的完整思路拆解

1.1 先弄清“子串”和“子序列”的区别

很多人刷题刷了很久，对这两个概念还是模糊的。子串是连续的，必须从一个位置一直延伸到另一个位置，中间不能断；子序列则允许跳过某些字符，只要保持相对顺序就行。hot100 里的子串题，全部依赖“连续”这个性质，正是这个性质决定了我们能用双指针和滑动窗口做线性扫描。如果题目换成子序列，DP 或回溯会成为主流思路，解法方向完全不同。这个区分看起来基础，实际上决定了做题方向。我见过不少人在一道题上耗了一两个小时，最后发现题目根本不是子串题，而是子序列题，方法选错，再怎么写都是浪费时间。

1.2 hot100 里子串题的分布与考察逻辑

我翻了一遍 hot100 的题单，子串相关的题大概集中在这么几道：无重复字符的最长子串、最小覆盖子串、找到字符串中所有字母异位词、和为 K 的子数组、滑动窗口最大值。题号分别是 3、76、438、560、239。这几道题出现在 hot100 不是巧合，它们分别对应了子串题的几种核心解法：滑动窗口配合哈希表、前缀和配合哈希表、单调队列。考察的不是单点死记，而是同一套思路在不同场景下的变形能力。面试官很少让你默写模板，但很喜欢把“找异位词”改成“找排列”，把“和为 K”改成“和为 K 的倍数”，本质没变，包装换了而已。

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 个元素的累加和，那么从 j+1 到 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 收缩来优化，必须完整扫描整个数组，就因为这个，很多面试者把滑动窗口硬套上去，结果样例对了、大数据超时。

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 的子串题量不算大，但每一道都值得反复咀嚼，这套东西吃透了，后面做任何窗口类的题目都会顺手很多。