企业官网建设流程全解析

热身题做得再顺，一进“面试经典150题”的滑动窗口专题，节奏还是会突然慢下来。刷到题41到题45这段时间，我最大的感受是：暴力解的代码谁都能写，但“为什么这个答案不超时”和“窗口扩到什么时候该收”才是真正决定你能不能举一反三的地方。

这篇文章不是那种逐个题目念题解的流水账，而是我刷题复盘时自己整理的一份笔记，重点放在解题思路的演变、边界条件的处理，以及这一组题目在真实面试里最常被追问的变形。适合正在刷算法题的应届生，也适合工作几年后想系统补数据结构基础的开发者。看完之后，你会明白滑动窗口不是一个需要背的模板，而是一套“用空间换时间”的思维模型。

1. 滑动窗口扫盲：从暴力枚举到窗口滑动的第一性原理

1.1 暴力做法的时间账，谁都能算但没人细算

以“无重复字符的最长子串”为例，如果不用任何技巧，最直接的做法是枚举所有起始位置，再从每个起始位置向后延伸，检查每一个子串是否满足条件。两层循环是 O(n²)，而每次检查是否有重复字符又要用集合或再次扫描，综合下来很容易到 O(n³)。

你可能觉得 n = 10⁴ 时三层循环只是慢一点，但真实面试题里的 n 经常是 10⁵ 甚至 10⁶，到这一步已经不是“慢一点”的问题，而是压根跑不出结果。我见过不少人在简历上写“熟悉常见算法”，却在一道最基础的子串题目上栽跟头，原因就是只会暴力，不理解窗口为什么能省下时间。

滑动窗口省时间的关键在于一个朴素事实：一个元素最多被“加入窗口”一次，也最多被“移出窗口”一次。这样原本 O(n²) 的扫描被压缩成 O(n)，每个指针都只在数组上单调向前走，不回头。这个单调性，是整个算法的根。

1.2 固定窗口和可变窗口，先分清再用模板

滑动窗口里最常见的两个子类型是固定窗口和可变窗口。固定窗口的长度在计算过程中不变，例如“找到字符串中所有字母异位词”里窗口长度始终等于模式串的长度；可变窗口则可以根据条件动态伸缩，例如“最短覆盖子串”里窗口右边不断扩张，左边不断收缩。

对应到代码上，两种窗口的骨架其实是一样的：

left = 0 for right in range(n): # 1. 把 nums[right] 纳入窗口 # 2. 如果当前窗口不满足约束，就收缩 left while left < right and 需要收缩: remove(nums[left]) left += 1 # 3. 此时窗口满足约束，可以在这里更新答案

这个骨架看起来简单，真正容易出问题的地方在于“收缩条件怎么写”以及“更新答案放在收缩之前还是之后”。我在后文逐个题目里会专门展开。

2. 题41 无重复字符的最长子串：别一上来就 while 删字符

2.1 这道题到底在考什么

题41就是经典的“无重复字符的最长子串”。题目给一个字符串 s，要求返回其中不含重复字符的最长连续子串的长度。

很多人的第一反应是：每次往窗口里加一个新字符，如果发现重复，就把左指针往右挪，一边挪一边把移出窗口的字符从集合里删掉，直到没有重复为止。这个思路没有问题，也是我推荐新手最先掌握的写法。

def length_of_longest_substring(s: str) -> int: left = 0 seen = set() ans = 0 for right, c in enumerate(s): while c in seen: seen.remove(s[left]) left += 1 seen.add(c) ans = max(ans, right - left + 1) return ans

这个版本最符合人的直觉：窗口里出现重复字符时，左指针一步步移动，把前面的字符逐个踢出去，直到重复被解决。每一步都是 O(1)，总体 O(n)。

但如果你足够细心，会发现这个写法在极端情况下会多做一些无用功。比如 s = "abcdecfgabc"，当遇到第二个 c 时，left 需要先经过 a、b，才能把 c 暴露出来。这些移除操作当然不贵，因为每个元素整体只会被移除一次，但有没有办法让左指针“跳”得更快呢？

2.2 用哈希表记住每个字符最后出现的位置

第二种解法是维护每个字符最近一次出现的下标。当窗口遇到重复字符时，直接把左指针跳到重复位置的下一位，而不是一步步挪。

def length_of_longest_substring(s: str) -> int: last_pos = {} left = 0 ans = 0 for right, c in enumerate(s): if c in last_pos and last_pos[c] >= left: left = last_pos[c] + 1 last_pos[c] = right ans = max(ans, right - left + 1) return ans

这个版本很容易写错的地方，就是那个last_pos[c] >= left的条件。我最初刷题时偷懒没加这个判断，结果遇到 s = "abba" 直接出问题。模拟一下：遍历到第三个字符 b 时，left 跳到 1，last_pos['b'] = 1；遍历到第四个字符 a 时，查表发现 a 之前出现在 0，但位置 0 早就不在窗口里了。如果不加>= left判断，会错误地再把 left 跳到 1，导致答案变成 1，而正确答案是 2。

这个细节虽然小，却是双指针类问题最容易踩的坑：历史位置和窗口当前位置之间是有差距的，不能用旧地图指导新旅途。

2.3 两种解法的取舍

Set + while版本理解成本低，代码不易出边界问题；哈希表跳转版本更快，代码也更简洁，但逻辑绕一点。面试时如果时间紧张，我推荐直接给第一个版本，同时主动说出第二个优化思路。面试官更看重你能不能把第一个版本解释清楚，而不是一上来就秀骚操作。

3. 题42 串联所有单词的子串：固定步长下隐藏的对齐问题

3.1 题目还原，先看关键条件

题42“串联所有单词的子串”给了一个主串 s 和一个单词数组 words，要求返回所有能由 words 中所有单词按任意顺序拼接而成的子串的起始下标。这里最重要的一个隐含条件：words 里的单词长度是相同的。

看到“任意顺序”，很容易想起排列组合，但真正的突破口恰恰是“所有单词长度相同”。这意味着，如果把窗口想成一段连续的子串，它本质上是由若干个等长单词块组成的。你可以把主串按单词长度切块，然后在一个由“单词”组成的序列上做滑动窗口。

3.2 为什么不能对每个起始位置都做一次哈希比较

最简单粗暴的思路是枚举主串里的每个位置作为起点，取 m 个单词长度，逐个取出单词并与 words 的计数比较。假设主串长度 n，单词个数 m，单个单词长度 w，那么对每个起点要切 m 个单词，检查一个窗口就是 O(m)，整体变成 O(n·m)，在主串很长时会被卡住。

一个比较聪明的做法是把窗口移动到“单词块”粒度上，每次跳过 w 个字符而不是 1 个字符。但这里有个容易忽略的问题：如果窗口从下标 0 开始，每次向后跳 w 个字符，你只能扫描到与下标 0 对齐的那些子串。可一个合法子串可能从 1、2、……、w-1 这些位置开始，它们和下标 0 不在同一个相位上。

3.3 分相位滑动，代码实现

因此解法要按起点偏移量分成 w 次循环，每次循环以 w 为步长扫描整个主串。下面是完整实现：

from collections import Counter from typing import List def find_substring(s: str, words: List[str]) -> List[int]: n = len(s) m = len(words) w = len(words[0]) total_len = m * w need = Counter(words) res = [] for start in range(w): left = start window = Counter() count = 0 for right in range(start, n - w + 1, w): word = s[right:right + w] if word not in need: window.clear() count = 0 left = right + w continue window[word] += 1 count += 1 while window[word] > need[word]: left_word = s[left:left + w] window[left_word] -= 1 count -= 1 left += w if count == m: res.append(left) return res

这段代码每次遇到不在 words 里的单词时，直接清空窗口并把 left 跳到 right 的下一格。这个操作背后的逻辑是：既然窗口不允许包含非法单词，那么所有横跨这个非法单词的子串全部失效，没必要再维护原来的窗口状态，清空是最安全的做法。

我写这道题时第一次栽在 start 循环的范围上。start 如果取到range(w)，每个相位都能覆盖完整，但窗口的 right 循环条件必须是range(start, n - w + 1, w)，否则会漏掉最后一小段。

3.4 复杂度分析与易错点

每个相位循环大约遍历 n / w 个单词，总共 w 个相位，所以总复杂度近似 O(n)。实际运行中 Python 的切片会有常数开销，但数量级是对的。这里要记住的核心是：遇到相同长度的单词组合，就用几种“相位”分别跑滑动窗口；这道题本质上是“对单词做数组滑动窗口”，而不是对字符做。

4. 题43 最小覆盖子串：一套模板打天下

4.1 题43的考点：最小覆盖子串

题43的经典程度在滑动窗口里可以排到前三：“最小覆盖子串”。给一个字符串 s 和一个字符串 t，要求在 s 中找到包含 t 全部字符的最短连续子串，返回这个子串。如果不存在，则返回空字符串。t 里可能包含重复字符。

这里最容易误解的是“覆盖”这两个字。覆盖不只是“出现过”，而是窗口里每个 t 中字符的出现次数都要不小于 t 中的对应次数。例如 t = "AABC"，窗口里要有两个 A、一个 B、一个 C，少于任何一个都算没覆盖。

4.2 双表 + 有效计数

标准的解法是维护两个哈希表：need记录 t 中每个字符的需求量，window记录当前窗口中各字符的出现次数。再用一个变量formed表示当前窗口中已经满足需求量的字符种类数。

当formed == len(need)时，说明窗口已经覆盖 t，此时尝试收缩左边，记录窗口长度，并更新全局最小结果。

def min_window(s: str, t: str) -> str: if not s or not t: return "" need = Counter(t) window = Counter() formed = 0 required = len(need) left = 0 ans = (float("inf"), None, None) for right, c in enumerate(s): window[c] += 1 if c in need and window[c] == need[c]: formed += 1 while left <= right and formed == required: if right - left + 1 < ans[0]: ans = (right - left + 1, left, right) removed = s[left] window[removed] -= 1 if removed in need and window[removed] < need[removed]: formed -= 1 left += 1 if ans[0] == float("inf"): return "" return s[ans[1]:ans[2] + 1]

4.3 为什么右扩张之后一定要跟着左收缩

这个模板看起来只是把之前的双重判断换了一种方式，但它真正蕴含的是一个不等式关系：只要窗口覆盖了 t，我们就把它保存下来，然后不断尝试收缩左边，看看还能不能继续保持覆盖。这种“能覆盖就尽量缩”的策略，保证了每个有效窗口都不会被漏掉。

我刷题时曾经疑惑：如果窗口中途变得非常长，formed 却一直不满足，那左指针始终不动，算法会不会漏掉某些更靠左的起点？不会。因为左指针只在窗口“已经满足覆盖”时才移动，当窗口不满足覆盖时，唯一正确的动作就是继续扩张右边，直到覆盖条件再次满足。也就是说，左指针已经到达的位置再也不需要回头，因为只要曾在某个时刻无法维持覆盖，把那部分左边界继续往右推才是最优路径。

4.4 这道题的真实边界陷阱

有几个边界值得单独拿出来说。第一，t 里全是同一个字符，例如 t = "aa"，need 里 'a' 的需求量是 2，窗口第一次遇到 'a' 时window['a'] == need['a']不成立，要第二次遇到才 formed+1。第二，窗口左边界移出字符时，如果该字符的需求量还没满足，formed 就必须立刻减 1，否则后续判断全部失真。第三，当 s 太大且 t 是一个很短的字符串时，最后结果可能是 s 本身或空串，这两种情况都要在返回时单独处理。

5. 题44与题45：两个方向都逃不出同一个窗口框架

5.1 题44 找到字符串中所有字母异位词：固定窗口的计数技巧

题44“找到字符串中所有字母异位词”给字符串 s 和模式串 p，要求在 s 中找到所有 p 的字母异位词的起始下标。异位词一串字符重新排列，所以要判断窗口是否和 p 有完全一致的字符计数。

因为英文字母只有 26 个，这里用两个长度为 26 的计数数组来代替哈希表，代码更清爽，数组比较也可能让复杂度更稳定。

def find_anagrams(s: str, p: str) -> List[int]: if len(p) > len(s): return [] target = [0] * 26 window = [0] * 26 n = len(p) for ch in p: target[ord(ch) - 97] += 1 for i in range(n): window[ord(s[i]) - 97] += 1 res = [] if window == target: res.append(0) for i in range(n, len(s)): window[ord(s[i]) - 97] += 1 window[ord(s[i - n]) - 97] -= 1 if window == target: res.append(i - n + 1) return res

这个解法本质上是固定窗口版本：窗口长度不变，每次只移动一格，加入一个新字符，剔除一个旧字符，然后比较两个计数数组。最容易写错的是新窗口起始下标的计算。假设窗口长度为 n，当前新字符下标是 i，那么被移除的旧字符下标是 i - n。如果你写成i - n + 1，窗口长度就不对了。

5.2 题45 长度最小的子数组：可变窗口的收缩时机

题45“长度最小的子数组”给一个正整数数组 nums 和一个正整数 target，要求找出和大于等于 target 的最短连续子数组的长度。

这道题比前几道简单，但它是“可变窗口按条件确定收缩时机”的最典型例子。窗口右端点每扩展一个数，就尝试用 while 循环收缩左端点，直到窗口总和小于 target。在收缩的过程中记录答案，就能得到最短长度。

def min_sub_array_len(target: int, nums: List[int]) -> int: n = len(nums) left = 0 total = 0 ans = n + 1 for right in range(n): total += nums[right] while total >= target: ans = min(ans, right - left + 1) total -= nums[left] left += 1 return 0 if ans == n + 1 else ans

这道题的代码看起来简单，但它有个很有价值的面试追问：如果数组里有负数，这个双指针解法还能用吗？答案是最好别用。因为负数会让数组和不再单调，窗口扩张后 total 可能变小，收缩后 total 反而可能变大，双指针的“指针单调移动”就不再正确。此时应该考虑前缀和加二分，或者更高级的数据结构。

5.3 两题的对照：固定窗口 vs 可变窗口

这张表也提醒我们，做滑动窗口题时先判断窗口长度是否固定，再决定要不要在答案更新时额外处理细节。很多人在题44上把“固定长度窗口”做成了“可变窗口”，然后不断删字符、加字符，反而把自己绕晕了。

6. 收官复盘：五个题踩出的窗口边界教训

6.1 循环不变量决定你是对还是错

五个题刷下来，我最大的收获是：写滑动窗口前必须先把循环不变量想清楚。你定义窗口是闭区间[left, right]还是半开区间[left, right)，直接决定left初始值是 0 还是 1，决定 while 循环里需不需要加等号，也决定最后返回子串时用s[left:right]还是s[left:right+1]。

Set + while的“删除窗口左端字符”写法里，我一开始习惯用半开区间，但更新答案时又用闭区间，导致几道题都差 1。后来统一成闭区间，每次扩展右边界后计算长度都用right - left + 1，才把所有题目跑顺。这不是天赋问题，是习惯问题。

6.2 我用五个题总结出的窗口问题自查清单

见到“子串/子数组/覆盖/异位词”等关键词时，我建议先按下面顺序过一遍：

• 窗口长度固定吗？固定则考虑“进一个、出一个”的固定窗口模型。
• 需要维护的是计数还是和？计数多用哈希表或数组，和多用数值变量。
• 什么时候该收缩左边界？不满足约束时，还是满足某个条件后继续尝试优化？
• 答案更新在收缩前还是收缩后？固定窗口一般是每次移动后；可变窗口一般在合法状态收缩中。
• 有没有历史记录和当前窗口冲突的情况？有的话加条件判断，别让过期位置干扰 left。

这五道题里，几乎每一道都在强迫你回答上面至少一个问号。题41考“过期位置”，题42考“相位划分”，题43考“收缩时机”，题44考“固定窗口和数组比较”，题45考“单调性与负数陷阱”，它们组合在一起，就是一轮完整的滑动窗口训练。

6.3 复杂度小结

我自己刷下来，最建议花时间去复盘的还是题43的最小覆盖子串，因为它把滑动窗口最精髓的部分浓缩成了一套模板。这套模板你掌握之后，再看其他滑动窗口题基本都有一种“脱衣服看骨架”的熟悉感。

最后再分享一个小技巧：调试窗口类问题时，不要在 IDE 里一路断点下去，直接在纸上把left、right、窗口内容和答案写出来，遇到第三步第五步就很容易看到问题出在哪。我靠这个方法，把五道题里所有“左一格右一格”的偏差全部修干净了。希望这份复盘对你也有效。