如果你正准备算法面试或者刚开始刷 LeetCode那么接雨水、无重复字符的最长子串、找到字符串中所有字母的异位词这三道题你迟早会正面撞上。它们常年出现在热门100题、高频题单和各类“leetcode刷题指南”里几乎每轮面试季都会被翻出来考。我也一样这三道题刷了不止一遍每次重刷都还能发现新的理解盲区。这篇文章就把我对这三道题的核心推导、代码细节、以及踩过的坑一次性讲透适合正在准备面试的人也适合想系统掌握双指针和滑动窗口的初学者。只要你把这三道题真正吃透后续很多窗口类问题都会轻松不少。1. 为什么这三道题值得放在一起刷1.1 三个题目分别对应哪套核心套路先给这三道题定个性。接雨水LeetCode 第42题考察的是双指针和边界最值的维护无重复字符的最长子串第3题是滑动窗口思想的入门必修课找到字符串中所有字母的异位词第438题是把滑动窗口和字符计数结合的经典题。它们经常被放进同一个题单不是偶然而是因为底层思维是连贯的用指针维护一个区间在区间状态变化中高效求答案。接雨水出现在热门100题的困难榜单上但它对面试来说真正的难度不是算法有多玄而是你能不能把“每个位置能接多少水”这个局部模型想清楚。一旦接受“水位由左右两侧较矮的一方决定”这个前提剩下的就是如何高效找出每个位置左右的最高柱子。无重复字符的最长子串是滑动窗口最经典的起点。它考察两个核心问题什么时候收缩左边界收缩后窗口是否仍然合法。这两个问题想明白后面做最小覆盖子串、滑动窗口最大值这类进阶题思路会顺很多。第438题则把滑动窗口从“变长窗口”推进到“定长窗口”。它跟第567题“字符串的排列”几乎是同一道题本质就是判断 s 中是否存在一个长度固定、字符构成与 p 完全相同的子串。这题常被用来考察你能不能把比较成本从 O(n*m) 压到 O(n)。三道题串在一起基本覆盖了双指针、滑动窗口、数组计数、哈希表这几个面试最高频的模块。如果你能不看题解写出这三道题的最优解并且把边界条件讲清楚面试官对你这块基本功基本就放心了。1.2 我建议用这个顺序刷我自己的刷题经验是不要完全按难度标签去刷而是按“套路专题”去刷。这三道题正好能组成一个小专题。先做无重复字符的最长子串把滑动窗口的收缩逻辑吃透接着做找到字符串中所有字母的异位词理解定长窗口如何维护计数最后啃接雨水体会双指针怎么在不知道全局最大值的情况下逐步逼近答案。这个顺序难度递增但思维是连续递进的。每道题做完后我还建议你强制自己写第二种解法。比如接雨水除了双指针再试试单调栈最长无重复子串除了 HashMap再试试数组桶异位词除了全量比较再试试计数器优化。同一个问题用两种思路写一遍比闷头刷十道新题有用得多。2. 接雨水从暴力到双指针的思维升级2.1 先把模型建对每个位置的水位由短板决定接雨水的题目描述很直白给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算下雨后能接多少雨水。我第一次做这题时错误地去想“整块水怎么求”结果越想越乱。正确切入点是把问题拆到每一根柱子上位置 i 能接的水等于min(左边最高柱子, 右边最高柱子) - height[i]。如果这个值是负数说明位置 i 本身就是凸起的能接的水是 0。这就是木桶效应。一个位置能不能存水要看左右两边有没有更高的柱子挡着。左右各取最高谁矮谁决定水面高度。例如 height [0,1,0,2,1,0,1,3,2,1,2,1]位置 2 高度是 0左边最高是 1右边最高是 3min(1,3) - 0 1所以这里能接 1 格水。位置 4 高度是 1左边最高是 2右边最高是 3min(2,3) - 1 1也能接 1 格。基于这个公式最直接的暴力做法是遍历每个位置分别向左向右扫描寻找最高柱子复杂度 O(n²)空间 O(1)。这个写法能帮你验证模型是否正确但面试时基本不合格。稍微优化一点用两个辅助数组 leftMax[i] 和 rightMax[i] 预先记录每个位置左侧和右侧的最大值一趟预处理加一趟遍历复杂度降到 O(n)空间升到 O(n)。很多新手能想到这里但面试官通常还会追问一句能不能把空间优化到 O(1)2.2 双指针推导为什么每次移动较矮一侧就是安全的双指针版的空间是 O(1)核心思路是维护 left 和 right 两个指针从数组两端向中间移动同时维护 leftMax左侧已扫描区域的最大值和 rightMax右侧已扫描区域的最大值。每次比较 height[left] 和 height[right]移动较矮的那一侧指针并在移动前计算该位置能接的水。以左侧为例当 height[left] height[right] 时我们处理 left 位置。此时右侧至少存在一根 height[right] 这么高的柱子水不会从右边流走。左侧这边leftMax 是已经扫描过的左侧最大值所以 left 位置的储水量可以直接用 leftMax - height[left] 来计算。如果 leftMax 比当前柱还矮说明左边也兜不住水差值小于等于 0记 0。反过来处理 right 位置时逻辑完全对称。这里有个很多人问过的点一个位置的储水量明明由左右两边最大值的较小者决定为什么只根据 leftMax 就能算关键在于我们永远优先移动“较矮侧”指针。当左侧出现一根超级高的柱子时右指针会一直被优先移动rightMax 也会不断更新直到两侧高度关系达到平衡。因此在处理 left 时右侧的潜在最高值不会小于 leftMax用 leftMax 作为水位是安全的。这个不变量不需要死记但值得在纸上自己推一遍。标准写法如下public int trap(int[] height) { int left 0, right height.length - 1; int leftMax 0, rightMax 0; int ans 0; while (left right) { if (height[left] height[right]) { if (height[left] leftMax) { leftMax height[left]; } else { ans leftMax - height[left]; } left; } else { if (height[right] rightMax) { rightMax height[right]; } else { ans rightMax - height[right]; } right--; } } return ans; }leftMax 的更新和累加分了两条分支当前柱比 leftMax 高时它自己成为新的左边界但位置本身不存水当前柱比 leftMax 矮时它左右都被更高的柱子包围存水量就是 leftMax - height[left]。你用官方示例 height [0,1,0,2,1,0,1,3,2,1,2,1] 在纸上跑一遍最终答案是 6重点观察指针移动的顺序和 leftMax、rightMax 的变化过程。2.3 边界条件与另一种解法单调栈接雨水的边界条件有几个容易踩的坑。第一个是数组长度小于 3 时直接返回 0因为至少需要三根柱子才能形成左右边界和一个凹槽。第二个是相等高度的处理height[left] height[right] 时走哪边分支都不影响答案但代码逻辑要保持一致。第三个是初始值leftMax 和 rightMax 最好从 0 开始而不是初始化为 height[0] 和 height[n-1]。虽然某些写法也能过但从 0 开始更贴合“还没扫描任何柱子”的语义不容易把边界想错。除了双指针接雨水还有个常见解法是单调栈。它的视角完全不同不是按位置算水量而是按“水平层”算水量。维护一个递减栈当遇到比栈顶高的柱子时弹出栈顶作为凹槽底部左边栈内元素是左边界当前柱子是右边界水平方向能接的水就是(min(左边界, 右边界) - 凹槽高度) * (右边界下标 - 左边界下标 - 1)。这个解法跟“柱状图中最大的矩形”的思路刚好反过来两道题放在一起对比学效率很高。不过双指针版空间 O(1)、逻辑也更直接面试时我个人会优先讲双指针单调栈作为补充方案提一下。3. 无重复字符的最长子串滑动窗口的入门必修课3.1 暴力法为什么会慢窗口又是什么第3题输入一个字符串要求找出其中不含有重复字符的最长子串的长度。朴素做法是枚举所有子串对每个子串判断是否有重复字符复杂度 O(n²) 甚至 O(n³)。判断重复字符本身可以用 HashSet但枚举子串的数量就是 O(n²)总体仍然太慢。滑动窗口的思路是把连续的一段字符看成“窗口”窗口左边界 left 和右边界 right 都从 0 开始right 不断向右扩张把新字符纳入窗口。如果新字符没在窗口中出现过窗口整体合法更新答案如果新字符已经在窗口里就向右移动 left把重复字符以及它左边的所有字符全部移出窗口直到窗口重新合法。为什么这个做法是线性的因为 right 从头走到尾每个字符最多被 right 加入一次、被 left 移出一次整体操作次数是 O(n)。与暴力法相比它不吃回头路这正是滑动窗口最核心的优化点用“单调移动”代替“反复枚举”。3.2 两种常见写法HashSet 收缩与 HashMap 跳跃第一种写法用 HashSet 保存窗口内字符这是滑动窗口最直观的模板public int lengthOfLongestSubstring(String s) { SetCharacter set new HashSet(); int left 0, ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); while (set.contains(c)) { set.remove(s.charAt(left)); left; } set.add(c); ans Math.max(ans, right - left 1); } return ans; }这种写法容易理解但 left 是一个一个挪的。虽然整体复杂度仍是 O(n)但面试追问“能不能优化”时HashMap 跳跃版才是更好的答案。思路是用 HashMap 记录每个字符最近一次出现的下标。遇到重复字符 c 时c 上次出现在 map.get(c)新的合法窗口至少要从 map.get(c) 1 开始。public int lengthOfLongestSubstring(String s) { MapCharacter, Integer map new HashMap(); int left 0, ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (map.containsKey(c)) { left Math.max(left, map.get(c) 1); } map.put(c, right); ans Math.max(ans, right - left 1); } return ans; }这里必须用 Math.max 和当前 left 取较大值原因很微妙。map 里记录的可能是很久以前的下标那个下标可能已经不在当前窗口内了如果直接把 left 设成 map.get(c) 1反而会把窗口错误扩张。我第一次写这个优化时就没加 Math.max拿用例 abba 一跑就出错了。当 right 走到第二个 a 时map 里记录的第一个 a 下标是 0而当前窗口其实是 [2,3]left 已经到 2 了。如果直接 left 0 1 1窗口变回 [1,3]那个含 bb 的非法区间就混进来了。所以记住left 只能往右跳不能往左退。3.3 字符集、空串和最后一个字符的细节这题有个容易被忽略的坑字符集不一定是 26 个小写字母。题目里的字符串可能包含字母、数字、空格、符号甚至中文。所以用new int[26]按 a 偏移是危险的更稳妥的做法是用 HashMap或者用长度 128 的数组覆盖 ASCII 范围。如果题目明确说只含小写字母再考虑 26 数组桶。空串和 null 也要处理。s 为 null 或长度为 0 时答案应该是 0。如果 s 长度是 1循环里 right - left 1 正好算成 1所以 ans 初始化为 0 是安全的。另外一个小细节无论新字符有没有重复ans Math.max(ans, right - left 1)都应该在每次 right 移动后执行一次保证最后一个字符带来的最长子串也被统计到。我见过不少人在循环里只在“无重复”分支更新 ans结果漏掉了末尾字符的情况。4. 找到字符串中所有字母的异位词定长窗口的计数问题4.1 异位词的本质与排序比较的缺陷第438题的描述是给定字符串 s 和 p在 s 中找到所有 p 的字母异位词的起始索引。所谓异位词就是字符种类和数量完全相同只是排列顺序不同的字符串比如 abc 和 bac 互为异位词。判断两个字符串是否互为异位词最省事的办法是分别排序后比较。但放在这个题目里就有点尴尬了如果对每个长度为 m 的子串都排序复杂度是 O(n * m log m)数据稍大就超时。正确直觉是子串长度固定为 p.length()问题就变成了一个定长滑动窗口。窗口从左往右滑每次滑动只涉及“右边进一个字符、左边出一个字符”。我们只需要维护窗口内每个字符的出现次数然后跟 p 的字符计数数组比较即可。比较两个长度为 26 的数组是否相等只需要 O(26) 时间基本可以当成 O(1)。4.2 基础写法两个计数数组 全量比较先给一个最容易理解的版本适合用来验证思路public ListInteger findAnagrams(String s, String p) { ListInteger ans new ArrayList(); int n s.length(), m p.length(); if (n m) return ans; int[] need new int[26]; for (char c : p.toCharArray()) need[c - a]; int[] window new int[26]; for (int i 0; i m; i) window[s.charAt(i) - a]; if (Arrays.equals(need, window)) ans.add(0); for (int i m; i n; i) { window[s.charAt(i) - a]; window[s.charAt(i - m) - a]--; if (Arrays.equals(need, window)) ans.add(i - m 1); } return ans; }这里的核心操作是“先加右边再减左边”。窗口的语义是 [i-m1, i]先加入 s[i] 使窗口临时变成长度 m1再移出 s[i-m] 恢复为长度 m。如果把减放在加之前窗口会先变短再变长虽然最终计数结果一样但中间态不容易读懂。我建议统一按“进一个、出一个”的顺序写这也是大多数题解使用的模板。注意最开始的窗口要先手动初始化初始化后就要马上比较一次因为起点索引 0 也可能是一个答案。我见过有人把初始化窗口和后面循环里的更新逻辑合并结果漏掉了 0 这个起始点。4.3 优化版用 need 计数器把比较压到 O(1)上面版本每次都要 Arrays.equals 比较两个长度为 26 的数组。虽然 26 很小但更优雅的做法是维护一个 need 变量表示“当前窗口还差多少个字符就能和 p 完全匹配”public ListInteger findAnagrams(String s, String p) { ListInteger ans new ArrayList(); int n s.length(), m p.length(); if (n m) return ans; int[] count new int[26]; for (char c : p.toCharArray()) count[c - a]; int left 0, right 0, need m; while (right n) { int rc s.charAt(right) - a; if (count[rc] 0) need--; count[rc]--; right; if (right - left m) { int lc s.charAt(left) - a; if (count[lc] 0) need; count[lc]; left; } if (need 0) ans.add(left); } return ans; }这个写法初次看有点绕拆开分析就清楚了。count 数组初始化时记录的是 p 中每个字符“还缺多少”。窗口每进入一个字符 rc就消耗一个缺口所以 count[rc]--如果消耗之前 count[rc] 是正数说明这个字符确实是 p 需要的need 减 1。窗口每移出一个字符 lc就归还一个字符count[lc]如果归还之前 count[lc] 是非负数说明这个字符之前是窗口为了匹配而“借”的need 加 1。当 need 0 时窗口恰好凑齐了 p 的所有字符需求又因为窗口长度恒等于 m所以必然是 p 的一个异位词。count[lc] 0这个判断是很多人的知识盲区。如果移出的字符在 count 中已经是负数说明这个字符是窗口里多出来的、p 根本不需要它移出它不会让 need 变小所以不需要 need。这个细节不搞清楚代码很容易把 if 判断写反。这套“need 计数器”技巧非常通用LeetCode 第76题“最小覆盖子串”的核心就是同一套东西区别只是那里窗口是变长的这里窗口长度固定为 m。把438题吃透再回去做76题难度会直接降一个等级。5. 三道题横向对比与刷题路线建议5.1 对比表格三道题的核心差异把三道题放一起看它们都围绕“指针 区间 状态”展开但各有侧重。我整理了一个对比表题目LeetCode编号核心技巧窗口特点时间复杂度空间复杂度接雨水42双指针 / 单调栈无窗口概念双端逼近O(n)O(1)无重复字符的最长子串3滑动窗口 哈希表变长窗口动态收缩O(n)O(字符集大小)找到字符串中所有字母的异位词438定长滑动窗口 字符计数定长窗口进一出O(n)O(1)从表里能看出两个核心模式接雨水考察的是“双指针 最值维护”后面两道题考察的是“滑动窗口 状态计数”。无重复字符是变长窗口的收缩问题异位词是定长窗口的进出问题两者正好互补。我在面试时讲这类题的策略是先讲思路再说复杂度最后手动跑一个短例子。比如接雨水跑 [0,1,0,2,1,0,1,3,2,1,2,1]异位词跑 scbaebabacd, pabc无重复字符跑 abcabcbb。能把一个例子从头到尾算对说明你是真的理解而不是背模板。5.2 从这三道题延伸出去的高频题这三道题是几个重要模块的“锚点”从它们能延伸到一大批高频题。从接雨水的单调栈延伸可以刷柱状图中最大的矩形84、每日温度739、接雨水 II407。从无重复字符的滑动窗口延伸可以刷最小覆盖子串76、滑动窗口最大值239、绝对差不超过限制的最长连续子数组1438。从异位词的计数窗口延伸可以刷字符串的排列567几乎同题、字母异位词分组49。如果时间有限我建议按“76 - 239 - 84”的顺序继续刷。76题最小覆盖子串是438题的进阶版把定长窗口改成变长窗口还要求记录最短窗口的左右边界涉及收缩时机的精细控制239题滑动窗口最大值引入了双端队列是窗口类问题里另一个重要分支84题则是把单调栈彻底吃透的必经之路。至于热词里提到的 994 腐烂的橘子、073 爱吃香蕉的狒狒跟这三道题不在同一模块。腐烂的橘子是 BFS/多源扩散的典型题爱吃香蕉的狒狒是二分答案的代表题建议单独归到“图论 BFS”和“二分搜索”专题里去刷别混在这一组滑动窗口专题里思维容易串。5.3 刷题时最容易踩的几个坑最后把我在这些题上踩过、也看别人反复踩过的坑汇总一下。第一个坑是变量命名混乱。很多人刷题喜欢用 i、j、k一到滑动窗口就分不清谁是左边界谁是右边界。我强烈建议统一命名成 left 和 right并在注释里写清楚窗口区间是闭区间 [left, right] 还是半开区间 [left, right)半开闭区间写错了会导致差一错误。第二个坑是上来就写最优解不做暴力验证。接雨水那题如果你先用 O(n²) 暴力跑通再用双指针优化你会很清楚双指针省掉了哪些重复扫描。反过来直接背双指针模板一旦面试官换个形状问你二维接雨水你大概率会被问住。第三个坑是只刷不总结。LeetCode 热门100题看起来很多但按套路分组后其实只有几十个模型。每道题提交通过之后花五分钟看一下高赞题解然后用自己的话在代码注释里写一遍思路比重复刷十道类似题的效果好得多。我现在刷题的习惯是每道题至少留两种解法一种最容易写对一种最节省空间。面试时先用容易写对的那版作答再主动提优化方向这样既能保证正确率又能展示思考深度。这三道题我前前后后重刷过很多遍每次重刷都会发现新的细节。尤其是接雨水的双指针安全性证明、无重复字符子串里 left 为什么必须取 max、异位词计数器里 count[lc] 0 的判断这些点不看题解很难一次想明白。如果你刷的时候也卡在这些地方不用怀疑自己这些都是正常的坎。把这三道题彻底吃透你收获的不仅是三个题解更是一整套处理区间问题的思维工具。