1. 为什么这三题值得放在一起刷先说个观察。我在带新人刷题、也帮朋友做面试模拟的时候几乎每隔几场就会碰到这三道题里至少一道。接雨水是字节、美团、阿里这些大厂的高频题无重复字符的最长子串基本是滑动窗口的“代名词”找到字符串中所有字母的异位词则是定长窗口和字符频次统计的标准题型。很多人的刷题方式是“一题一题刷”刷完就忘。但把这三题放在一起看你会发现它们并不是孤立的而是同一条思维主线的三次变奏用线性扫一遍替代暴力枚举通过维护某种“状态”来避免重复计算。无重复字符的最长子串是“动态伸缩窗口 字符最近出现位置”的状态维护找到字符串中所有字母的异位词是“定长窗口 字符频次差异”的状态维护接雨水则是“左右两侧边界极值”的状态维护它甚至也可以写成双指针形态。理解了这条主线你刷的就不是三道题而是一类题。这篇文章就把这三道题串起来讲透包括暴力思路为什么不可行、最优解是怎么一步步推出来的、代码里哪些细节容易踩坑以及面试官常见的追问方向。适合正在准备算法面试、或者刷LeetCode热题100卡壳的人也适合刷完题但没想明白“为什么要这么做”的人。2. 无重复字符的最长子串滑动窗口的入门必修课2.1 暴力解法的时间账题目本身很简单给定一个字符串找出其中不含重复字符的最长子串的长度。比如abcabcbb的答案是3对应abc。很多第一次刷到这道题的人第一反应是我枚举所有子串判断每个子串里有没有重复字符取最长的那个不就行了确实可行。但代价很高枚举所有子串是 O(n²)判断子串是否含重复字符是 O(k)k 为子串长度整体是 O(n³)。字符串长度稍微上来一点比如10^5级别这个思路直接报废。问题是我们真需要枚举所有子串吗仔细想一下以某个位置为起点一旦我们找到了第一个导致重复的字符这个起点更长的子串就都不用看了。因为它们都包含重复字符不可能成为答案。暴力解法浪费就浪费在它把已经判定无效的区间又重复扫了很多遍。这就是窗口思想出现的动机让起点和终点都只往前走不回头。2.2 窗口是怎么“滑”起来的滑动窗口的核心是把“子串”抽象成一个左边界left和右边界right之间的区间。每次把right往右扩展一格区间内就多一个字符。如果发现这个新字符在区间内已经出现过说明当前窗口已经不合法那我们就需要移动left把窗口收缩到合法状态。关键问题在于怎么高效判断“当前字符在窗口内是否出现过”最简单可靠的方式是用一个数组或哈希表记录每个字符最近一次出现的下标。比如用一个mapchar, int每次遇到字符c先查一下它上次出现在哪。如果上次出现的位置lastPos[c]大于等于当前的left说明这个字符就在窗口内部窗口需要收缩。收缩到什么位置不是一步步往右挪而是直接把left跳到lastPos[c] 1。这个跳跃是“无重复字符的最长子串”和后面两道题最大的不同点它跳的是位置不是频率。看个例子。字符串abba扫描到a(0)记录 lastPos[a] 0扫描到b(1)记录 lastPos[b] 1扫描到b(2)发现 lastPos[b] 1大于等于 left(0)所以 left 跳到 2更新 lastPos[b] 2扫描到a(3)发现 lastPos[a] 0但此时 left 2lastPos 小于 left说明窗口内其实没有重复的 a所以不收缩只更新 lastPos[a] 3。最大长度是 2ab或ba。这里有个很容易写错的细节判断重复时不仅要看字符是否出现过还要看它的上次出现位置是否在当前窗口范围内。很多人写成“只要出现过就移动 left”结果在abba上会算出错误答案。正确的判断条件就是if lastPos[c] left: # 说明 c 出现在窗口内 left lastPos[c] 12.3 代码模板与复杂度下面是 C 实现class Solution { public: int lengthOfLongestSubstring(string s) { vectorint lastPos(128, -1); // ASCII 字符记录最近出现下标 int left 0, ans 0; for (int right 0; right s.size(); right) { char c s[right]; if (lastPos[c] left) { left lastPos[c] 1; } lastPos[c] right; ans max(ans, right - left 1); } return ans; } };能用一个定长int[128]就用它别用unordered_map。字符集是确定的数组访问是 O(1) 且常数极小哈希表虽然也是 O(1)但常数大得多在最长字符串上能明显感觉到差距。复杂度很干净时间 O(n)每个字符最多被 left 和 right 各扫过一次空间 O(|字符集|)这里就是 O(128)可以认为是常数。2.4 几个容易翻车的边界第一空串。长度是 0代码里循环根本没进去ans 初始化为 0没问题。但如果你把 ans 初始化为INT_MIN空串就会出错。第二全相同字符比如bbbb。每次遇到 blastPos 都大于等于 left所以 left 一直跳到当前 rightans 始终为 1。这个没问题但值得手推一遍确认。第三ASCII 之外的情况。LeetCode 原题默认是 ASCII 字符但如果你用int[128]遇到中文或扩展字符会越界。稳妥做法是直接用int[256]或者干脆用unordered_mapchar,int避免因为字符编码问题翻车。讲到这里多说一句滑动窗口不是“背模板”就能会的它的核心是想清楚 left 什么时候动、动到哪里。这一题里 left 跳的是“重复字符上次出现位置的下一个”下一题里 left 动的逻辑完全不同注意对比。3. 找到字符串中所有字母的异位词定长窗口与计数比较的配合3.1 题目本质不是“排序比较”题目要求给定两个字符串s和p在s中找到所有p的异位词的子串返回这些子串的起始索引。异位词就是相同字符集合、相同频次但排列顺序不同的单词比如abc和bca、cab都是异位词。第一次做这道题最直觉的想法是对p排序然后枚举s中每个长度等于len(p)的子串排序后和排序后的p比较。排序后相同就是异位词。这个思路能过小数据但问题很大每次枚举子串排序是 O(k log k)k 是p的长度整体 O(n k log k)遇到长字符串直接超时。而且排序比较的思路没法扩展到更复杂的题型。正确方向是计数比较异位词的本质就是频次分布一致。不需要关心字符顺序只需要统计窗口里每个字符出现了多少次和p中每个字符的出现次数做对比。相同就是异位词。3.2 用 differ 变量代替每次全量比较如果我们每次滑动窗口都重新统计窗口内字符频次再和p的频次数组逐位比较复杂度是 O(n × 26)假设只有小写字母其实也可以用。但更优雅的写法是维护一个differ变量表示当前窗口内频次与目标频次不一致的字符个数。做法是先统计p的频次到count[26]。然后初始化s的第一个窗口每遇到一个字符count[c]--。count的含义从“p中每个字符的频次”变成了“p的频次与当前窗口频次的差值”。如果count[i] 0说明这个字符在窗口和 p 中频次一致如果count[i] ! 0说明不一致。每次滑动窗口时右边界新进入一个字符ccount[c]--左边界离开一个字符dcount[d]。维护differ的方式是在每次增减前后判断count是否从 0 变成非 0、或者从非 0 变成 0。如果从 0 变成非 0differ从非 0 变成 0differ--。当differ 0时说明窗口内频次和p完全一致当前起始位置就是一个答案。这个技巧很多题解里叫“diff 计数器”是滑动窗口进阶里很常用的优化。它能帮你把每次比较从 O(26) 降到 O(1)代码还更简洁。3.3 完整实现与细节用 C 实现如下class Solution { public: vectorint findAnagrams(string s, string p) { vectorint res; int lenS s.size(), lenP p.size(); if (lenS lenP) return res; vectorint count(26, 0); for (char c : p) count[c - a]; // 初始化第一个窗口 for (int i 0; i lenP; i) { count[s[i] - a]--; } int differ 0; for (int i 0; i 26; i) { if (count[i] ! 0) differ; } if (differ 0) res.push_back(0); // 滑动窗口 for (int i lenP; i lenS; i) { // 左侧滑出 int outIdx s[i - lenP] - a; if (count[outIdx] 0) differ; count[outIdx]; if (count[outIdx] 0) differ--; // 右侧滑入 int inIdx s[i] - a; if (count[inIdx] 0) differ; count[inIdx]--; if (count[inIdx] 0) differ--; if (differ 0) res.push_back(i - lenP 1); } return res; } };这段代码里有个很隐蔽的细节先处理滑出的字符再处理滑入的字符顺序不能乱。因为滑出和滑入可能作用于同一个字符虽然大多数情况下结果一样但为了避免逻辑混乱还是固定先出后进。另外要注意differ的更新条件。写成“如果当前值从 0 变成非 0differ从非 0 变成 0differ--”就一定对。不要写成“如果当前值变成 0 就减一变成非 0 就加一”这样没考虑增减前的状态会出错。3.4 复杂度与常见误区时间 O(n)空间 O(1)固定 26 长度的数组。整体性能非常好。容易踩的坑有三个第一个忽略lenS lenP的情况直接返回空数组。不判断的话初始化窗口那块就越界了。第二个differ更新时机写错。我见过很多人把 diff 更新放在滑动之后“重新计算一遍差异”那样复杂度反而退化了还不如老老实实用全量比较。第三个题目说的是“字母”异位词有没有说都是小写LeetCode 原题明确说是小写字母直接用- a可以。但如果你在面试中遇到变种比如大小写混合就得把数组开到 128 或者用哈希表先跟面试官确认字符集范围再动手。3.5 和无重复字符的最长子串的对比这两道题放在一起学特别有价值因为它们都是滑动窗口但窗口的伸缩策略完全不同维度无重复字符的最长子串找到所有字母异位词窗口长度动态伸缩固定等长状态内容字符最近出现位置字符频次差值左边界移动条件遇到窗口内重复字符每次固定右移一格判定答案每次移动后取最大值differ 0 时记录起点看出差别了吗所谓“滑动窗口”并不是只有一种写法。它的核心是用窗口框住一段连续区间然后通过维护某种状态来判断窗口是否满足条件。状态维护得越巧妙代码就越简洁。4. 接雨水从双指针到单调栈的状态维护思维4.1 先把物理模型想清楚接雨水的题面给定一个非负整数数组height每个元素表示宽度为 1 的柱子的高度问这些柱子之间能接多少雨水。举例[0,1,0,2,1,0,1,3,2,1,2,1]答案是 6。这题之所以经典是因为它涉及到一个核心认知一个位置能接多少水取决于它左右两侧柱子高度的较小最大值减去当前柱子高度。也就是rain[i] max(0, min(maxLeft[i], maxRight[i]) - height[i])为什么是“较小”的那个最大值因为水往低处流两侧最高的柱子决定了这个凹槽最多能存到多高的水位。水位不可能超过较矮那一侧的封顶高度。如果左侧最高是 3、右侧最高是 5那么这个位置的水位最多到 3超出 3 的部分会从左侧流走。这个公式是所有解法的出发点。暴力做法就是先从每个位置分别向左向右扫一遍找出左右最大值再套公式累加。复杂度 O(n²)能过但不优雅。4.2 双指针解法最优且最需要理解边界双指针解法的精妙之处在于我们不需要提前把所有位置的最大左值和最大右值都算出来只需要维护两个变量leftMax和rightMax在用两个指针从两侧向中间逼近的过程中一边走一边计算。核心逻辑很简单left从最左开始right从最右开始如果height[left] height[right]说明left位置的右侧已经有一个“屏障”高于当前左侧最高柱子那left位置接水量只由leftMax决定可以结算left反之则由rightMax决定结算right。很多人第一次看到这个解法会困惑凭什么height[left] height[right]时就能确定left位置的右最大是height[right]关键在这里我们维护的rightMax记录的是从 right 指针到现在扫过的所有位置的最大值也就是height[right]及其右侧所有柱子的最大高度。如果height[left] height[right]那么不管right右边还有什么更高的柱子min(leftMax, rightMax)这个值中左侧的上限必然以leftMax为准因为leftMax height[left] height[right] rightMax。所以此时左边的水已经可以确定左指针往右走不会错过答案。反之如果height[left] height[right]说明右边界高度不够需要用右侧的逻辑右指针往左走。文字有点绕配合一块代码看就很清楚class Solution { public: int trap(vectorint height) { int left 0, right height.size() - 1; int leftMax 0, rightMax 0; int ans 0; while (left right) { if (height[left] height[right]) { leftMax max(leftMax, height[left]); ans leftMax - height[left]; left; } else { rightMax max(rightMax, height[right]); ans rightMax - height[right]; right--; } } return ans; } };注意ans leftMax - height[left]这里不需要max(0, ...)因为leftMax在更新之后一定 height[left]。如果写成max(0, ...)也能跑但会显得你对这个逻辑不够有把握。4.3 单调栈解法另一种常见书写方式双指针是最优解但面试时你很可能还会被问到“还有没有其他做法”或者你自己需要理解题解区里另一种主流写法——单调栈。单调栈的思路是维护一个递减的柱子高度栈栈底到栈顶单调递减即柱高从大到小。当遇到一个比栈顶柱子更高的柱子时说明出现了一个“凹槽”的右边界可以结算水量。具体做法是遍历height如果当前柱子高度height[i]小于等于栈顶柱子高度就把i入栈如果height[i]大于栈顶柱子高度就说明栈顶位置柱子右侧出现了更高的柱子可以尝试形成凹槽弹出栈顶它的高度记为bottomH此时新的栈顶是凹槽的左边界当前 i 是右边界凹槽的高度是左右边界中较矮的减去弹出的底部柱高水量 宽度当前 i 到新栈顶的距离减 1 × 高度差如果弹出后栈空了说明没有左边界凹槽无法形成不需要结算。class Solution { public: int trap(vectorint height) { stackint st; // 存柱子的下标 int ans 0; for (int i 0; i height.size(); i) { while (!st.empty() height[i] height[st.top()]) { int bottom height[st.top()]; st.pop(); if (st.empty()) break; int left st.top(); int width i - left - 1; int boundedHeight min(height[left], height[i]) - bottom; ans width * boundedHeight; } st.push(i); } return ans; } };我第一次看这个解法时最大的困惑是为什么要一层一层结算为什么不能直接算整段原因是凹槽是有层级的。比如[3,1,2,1,4]位置 1 和 3 的“坑”里能接水的容积分为两层单调栈用弹出栈顶的方式一层层剥开每一层对应一个可确定的水平面这样累加就是准确的。两种解法对比维度双指针单调栈时间复杂度O(n)O(n)空间复杂度O(1)O(n)核心变量leftMax / rightMax栈内柱子下标理解难度边界较难理解结算过程较绕代码量较少略多面试建议优先写双指针因为它空间更优、代码更短。但如果你对单调栈比较熟也可以先讲单调栈再补充双指针版本展示你理解多种方案。4.4 接雨水的高频失误点最容易翻车的坑是“只判断了当前柱子高度忘了判断边界是否存在”。双指针版一般不会出这个问题因为 left 和 right 天然就是边界。单调栈版则要注意弹出栈顶后如果栈为空表示没有左边界直接 break不能继续算。还有一个理解层面的常见误区有人认为双指针解法是“按柱子逐个结算”实际上它是“按柱子逐个结算但每个柱子结算的水量已经由当前可确定的边界锁定了”。这些边界值不需要预先计算因为指针移动的方向保证了信息足够。最后一个实战心得如果面试考到接雨水强烈建议先把暴力公式写出来也就是rain[i] max(0, min(maxLeft[i], maxRight[i]) - height[i])。这会让面试官知道你理解的是本质而不是背了双指针代码。然后再推演到双指针面试体验会好非常多。5. 面试实战追问链与代码规范5.1 面试官会怎么追问这几道题在面试中很少只问“写代码”。高频追问大致有这么几类第一类复杂度追问。“你这解法复杂度多少还有没有更优的”接雨水的双指针已经是 O(n) 和 O(1) 了面试官大概率满意。但异位词那题如果你用了排序比较就要准备好接受“能不能不用排序”的追问然后引出频次统计和 differ。第二类边界场景。“如果输入是空串呢”“如果 p 比 s 长呢”“如果全部是同一个字符呢”这些就是前面提到的边界条件写之前和写完都要自己先检查一遍。第三类变体设计。“如果找的是最长无重复字符的异位词你怎么改”“如果把异位词改为回文串呢”这时候你在第 2、3 题里建立的“窗口 状态”思维就可以直接复用改窗口伸缩规则改状态定义复杂度框架不用变。第四类为什么不选另一种方案。接雨水里“为什么不用单调栈”“单调栈和双指针的区别”是常见追问点。异位词里“为什么要用 differ 变量而不是每次全量比较”。这些问题考验的不是背书能力而是对每个解法成本和收益的真实理解。5.2 易混淆场景对照表刷题群和评论区里这三道题最高频的混淆点是题目表面相似点实际差异无重复字符的最长子串 vs 异位词都涉及字符出现位置/频次前者动态伸缩、看位置后者定长、看频次接雨水双指针 vs 最长回文子串双指针都是左右指针夹逼接雨水维护的是最大高度不是回文条件单调栈 vs 单调队列都是维护有序结构接雨水用单调栈滑动窗口最大值用单调队列不要混如果你能在面试时说出“这题是滑动窗口的变体和最长无重复子串的区别在于窗口定长、状态是频次”面试官会立刻知道你做过系统的总结而不是东一榔头西一棒子地刷题。5.3 一种好用的面试书写习惯我在面试时写滑动窗口习惯先写四个要素再补代码窗口是什么左闭右开区间 [left, right) 窗口的扩张规则right 每次右移一格 窗口的收缩规则何时、如何移动 left 状态怎么维护用什么数据结构、何时更新先把这四个要素在草稿纸上写清楚再动手写代码。代码只是把思路翻译成语言。这个方法对这三道题都适用也能帮你应对面试中的变体题。6. 举一反三这三题背后的思维模型还能打哪些题6.1 滑动窗口模型的扩展无重复字符的最长子串用的是“动态伸缩窗口”这个模型可以直接迁移到很多题比如最小覆盖子串同样用窗口 频次统计但 left 收缩条件变了不再是“出现重复”而是“窗口已经覆盖了 t 中所有字符尝试收缩以变得更短”替换后的最长重复字符给窗口加一个“最多可替换 k 次”的限制核心就是维护窗口内某个字符的最大频次判断是否满足长度 - 最大频次 k爱吃香蕉的狒狒这类题虽然外层是二分但判断某个速度是否够快的函数内部也用到了类似的数学建模和边界思维可以顺手练一练二分答案的思路。6.2 计数差异模型的扩展找到字符串中所有字母的异位词用了“频次差值 differ”的模型。这个模型还能打不少题字符串中的所有回文串计数虽然要结合中心扩展但判断异位词那套频次比较思路常被用来构造某些回文判定前的预处理排列Permutation in String其实就是异位词题目的变种判断 s 中是否存在一个子串是 p 的排列代码几乎一模一样最大连续1的个数 III也可以理解为“窗口内 0 的个数不超过 k”的状态维护和 differ 维护异曲同工。6.3 双指针夹逼模型的扩展接雨水的双指针本质是“左右边界信息足够时结算一侧并移动该侧指针”。这个模型和“盛最多水的容器”几乎是一个模子刻出来的while (left right) { ans max(ans, min(height[left], height[right]) * (right - left)); if (height[left] height[right]) left; else right--; }两题都是根据较矮的一侧来决定移动哪边指针。区别只在于接雨水计算的是“累积接水量”盛水容器计算的是“两柱之间最大面积”。把这两题对比着做一遍双指针夹逼的手感会强很多。另外像 LeetCode 994 腐烂的橘子这样的 BFS 题虽然框架和滑动窗口差别很大但它也包含“状态随时间/蔓延扩散”的维护思想把初始腐烂的橘子作为多源 BFS 的起点逐层向外扩散记录每个格子被感染的时间。如果你已经把接雨水的“边界状态维护”想清楚了理解多源 BFS 会更容易因为核心都是“在状态变化过程中确保每个节点只被处理一次”。6.4 一道串起三题的综合题如果要给自己加难度可以试试这道综合题“给定一个字符串 s找到其中不含重复字符的、且字符频次与目标串 p 的某个排列完全一致的最长子串。”它同时要求你处理“字符重复”和“频次一致”两个约束滑动窗口的 left 收缩条件要同时考虑位置和频次。这种题在真实面试中不多但非常适合用来自测如果你能一步步把约束拆开分别用位置哈希和频次 diff 处理说明你对滑动窗口的理解已经从“背模板”变成了“会设计”。7. 一些刷题习惯上的个人心得最后分享几条自己刷了几年题、也带过不少人之后形成的习惯不一定适合所有人但可以参考。第一同一类题不要只刷一道。很多人刷完“无重复字符的最长子串”就觉得自己会滑动窗口了遇到异位词又不会了。问题就出在只记住了代码没记住“窗口伸缩规则是由题目约束决定的”。我的习惯是刷完一道题立刻找同类的两三道题做一遍对照差异。第二隔一段时间重写一遍。接雨水这道题我非常推荐每两周重写一次双指针版本直到能闭着眼睛写出并解释清楚“为什么height[left] height[right]时左边可以结算”。如果做不到说明你还没真正掌握。第三把代码写出“给人看的版本”。刷题时我们的代码只要通过就行但面试里的代码要能讲清楚。变量名用left/right、leftMax/rightMax注释写清“窗口收缩条件”“答案统计时机”这些关键行面试官和未来的你自己都会感谢你。第四不要盲目追求“最优解”。最优解当然要知道但暴力解、次优解也要会写。面试时先给暴力思路再优化比直接甩一个精妙的双指针更显得思维完整。我在模拟面试中见过不少人直接写最优解但被追问“为什么正确”时支支吾吾这种反而最掉分。这三道题本质上就是三种“状态维护”的典型示范位置状态、频次状态、边界极值状态。想明白这一层再去刷其他题你会发现很多题都是老朋友换了个马甲。以后刷到新题时可以下意识问自己一句“这题要维护什么状态是位置、频次、还是边界极值”答案有了解法基本就有方向了。