手撕算法这四个字几乎每个面过试的人都懂。白板或共享屏幕上只有一道题没有自动补全没有编译器帮你兜底你需要在十几分钟里写出能跑、能把思路讲明白的代码。而在所有“被撕频率”最高的题目里滑动窗口绝对是排在第一梯队的东西——尤其是3. 无重复字符的最长子串和438. 找到字符串中所有字母异位词这两道题我见得太多次出现在面试题单里了从字节到微软从实习到社招换着花样考。这两道题放在一起刷价值远大于“多做了两道题”。它们一个是不定长窗口一个是定长窗口一个是找最长一个是找所有匹配起点恰好覆盖了滑动窗口最核心的两种用法。把这两道吃透你就能顺手解决最小覆盖子串、字符串排列、最长连续不重复子序列这些变体。这篇文章我会从暴力解法的死穴讲起逐步拆到滑动窗口的直觉来源和标准写法再把438题那个“用计数数组替代哈希表”的细节给你掰开揉碎最后补上我自己刷这些题时踩过的坑以及面试时怎么一步步把思路讲给面试官听。1. 这两道题为什么必须放在一起刷刷LeetCode最怕的不是题难而是刷完就忘。今天会了第3题明天碰到438题又觉得是“新题”其实这两道题的底层逻辑是同一套东西只不过换了层皮。把它们放在一起对比着学远比单独刷十道类似的题更高效。1.1 “连续子串”问题的共同死穴先看这两道题的共同点都是在一个字符串里找连续的子串都要求时间复杂度尽量接近O(n)。如果你没用过滑动窗口第一反应大概率是暴力枚举。第3题暴力做法是枚举所有子串再判断每个子串内部有没有重复字符复杂度O(n²)甚至O(n³)。第438题更惨枚举s中所有长度为len(p)的子串再逐个比较每个子串的字符频次复杂度O(n·m)其中m是p的长度。一旦字符串长度上到十万级别这种写法直接超时。这就是“连续子串”类问题的死穴相邻子串之间有大量重叠信息暴力解法把这些信息全浪费了。比如第438题里窗口从[0, 3)滑到[1, 4)只多了一个字符、少了一个字符你却重新统计了一遍全部字符出现次数这不是白干活吗1.2 滑动窗口的直觉不该从头再来滑动窗口想解决的问题只有一个——别反复从头扫描。想象你拿着一把尺子在字符串上量长度。尺子右边每向右移动一格左边不一定动当窗口内的状态不满足要求时左边才被迫收缩。整个过程里你只需要维护窗口两端的指针和一份“窗口当前状态”的记录就能做到每个字符最多被进出窗口各一次整体复杂度降到O(n)。第3题和第438题恰好演示了滑动窗口的两种典型节奏第3题是可变窗口右指针不断右移遇到重复字符时左指针跳到正确位置窗口的长度动态变化每次移动后更新答案。第438题是定长窗口窗口长度固定为len(p)右指针每右移一格左指针也必跟着右移一格窗口像一条固定长度的履带向前滚动每次移动后检查窗口内容是否合法。这两种节奏只要都亲手写过一遍以后看到“子串”“连续”“最长/最短/所有位置”这些关键词脑子里自然会浮现出左右指针的轮廓。1.3 一个模板吃透一大类我自己刷了三百多道题之后总结出一个经验大部分滑动窗口题都能用同一套模板框架稳住再按题目微调。先记这个骨架初始化左右指针 left 0, right 0 初始化窗口状态哈希表/数组/计数器 初始化答案 while right len(s): 把 s[right] 纳入窗口状态 while 窗口不满足条件: 把 s[left] 移出窗口状态 left 1 更新答案 right 1第3题就是在“窗口不满足条件”这步做文章第438题则是在“更新答案”这步做文章。你把这套骨架刻在脑子里下面两道题的所有代码都只是往里面填细节。2. 第3题无重复字符的最长子串——窗口收缩的时机是核心这道题是滑动窗口的人门题也是面试官最爱拿来“热场”的题。它本身不难但想一遍写对并不容易因为窗口收缩的逻辑里藏着两个非常微妙的边界点。2.1 题目本质最长连续区间题目要求给定字符串s找出其中不含重复字符的最长子串长度。什么叫“子串”必须是连续的。abc的子串是a, ab, abc, b, bc, c但ac不是子串它是子序列。这个区分很重要因为“连续”正是滑动窗口能用的前提。输入abcabcbb答案是3因为最长无重复子串是abc长度3。输入bbbbb答案是1。输入pwwkew答案是3对应wke或kew。2.2 关键突破口用哈希表记录每个字符最近出现的位置网上很多解法用Set或数组来“判断字符是否出现过”但真正优雅的做法是记录字符最近一次出现的下标。为什么因为窗口收缩时你需要知道左指针到底该跳到哪。举个具体例子。s abba右指针走到第3个字符a时发现a之前出现过而且位置是0。这时候左指针应该跳到哪里如果你只知道“出现过”你可能会把左指针跳到1那就错了——因为窗口内[1, 3]是bb显然不对。正确做法是让左指针直接跳到上一次出现位置的下一个位置即0 1 1。等一下这里有个陷阱。abba在第2个字符时左指针已经因为重复的b从0跳到了2或者写成跳到上次b出现位置的下一位即1 1 2。到第3个字符a时a上次出现的位置是0但0已经在窗口外面了你还能把左指针跳到0 1 1吗不能因为那会让左指针回退窗口就乱套了。这就是这道题第一个关键点左指针只能往右走不能回退所以要取max(左指针当前位置, 上次出现位置 1)。2.3 完整的解题步骤有了上面这个认知代码其实就三部分右指针从头到尾遍历字符串记录每个字符最近一次出现的位置。遇到重复字符时根据“上次出现位置 1”和当前左指针位置取较大值更新左指针。每次迭代都计算right - left 1维护一个最大值作为答案。Python代码def lengthOfLongestSubstring(s: str) - int: char_index {} left 0 ans 0 for right, ch in enumerate(s): # 如果字符出现过并且出现位置还在窗口内 if ch in char_index and char_index[ch] left: left char_index[ch] 1 # 记录/更新字符最近出现位置 char_index[ch] right # 更新最长长度 ans max(ans, right - left 1) return ansJava版本class Solution { public int lengthOfLongestSubstring(String s) { MapCharacter, Integer lastIndex new HashMap(); int left 0; int ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (lastIndex.containsKey(c) lastIndex.get(c) left) { left lastIndex.get(c) 1; } lastIndex.put(c, right); ans Math.max(ans, right - left 1); } return ans; } }char_index[ch] left这个判断就是防止左指针回退的保险栓。有了它你可以放心地处理abba这种左指针已经右移过的场景。2.4 为什么使用数组替代哈希表如果字符串只包含ASCII字符也就是256个以内的字符集可以用长度256的数组替代哈希表速度更快更适合面试手撕。def lengthOfLongestSubstring(s: str) - int: last [-1] * 256 left 0 ans 0 for right, ch in enumerate(s): idx ord(ch) if last[idx] left: left last[idx] 1 last[idx] right ans max(ans, right - left 1) return ans数组的优势是没有哈希冲突、没有装箱开销在字符集固定的场景下是更好的选择。但要注意如果题目没说明字符集范围用哈希表更稳妥。面试时可以先问一句“字符集是ASCII还是Unicode”这既是专业性的体现也能帮你决定数据结构。2.5 这道题最常见的三个边界错误我批改过很多人的代码发现错误集中在这三个地方错误一更新左指针时忘记取max。直接写left last[ch] 1处理abba这种用例时左指针回退答案直接错。这是最经典的错误没有之一。错误二更新字符位置放在判断之前。先记录char_index[ch] right再判断重复会导致判断时字符位置已经是当前位置char_index[ch] left永远成立左指针每次都跳到right 1窗口永远长度为0。错误三循环结束后才更新答案。漏掉最后一个窗口的统计。比如字符串abc如果只在收缩时才更新答案最后返回0。正确思路是每次右指针移动后都更新一次答案因为窗口可能随时变大最大值不会只在收缩时出现。3. 第438题找到字符串中所有字母异位词——定长窗口的另类玩法第3题如果你写顺了第438题其实很难做错但前提是你得扭转一个思维定式前面是窗口长度变化这里窗口长度从头到尾都是固定的。3.1 题目本质窗口长度固定为len(p)题目要求给定字符串s和p返回s中所有p的异位词的起始索引。异位词指字母相同、排列不同的字符串。比如s cbaebabacd, p abc输出[0, 6]。位置0的子串cba是abc的异位词位置6的子串bac也是。而位置2的aeb虽然有三个字符但字符集不同不是异位词。暴力做法枚举s中所有长度等于len(p)的子串对每个子串统计字符频次和p的频次比对。时间O(n·m)空间O(1)或O(m)。这当然能过小数据但面试官一定会追问“能不能优化到O(n)”。3.2 核心思想字符频次数组字母异位词的判断不需要排序只需要比较两个字符串中每个字符出现的次数是否相等。因为题目明确给的是小写字母LeetCode原题限制s和p只包含小写英文字母你可以直接用长度26的整数数组下标0对应a1对应b依此类推。用p_count保存p的字符频次用s_count维护当前滑动窗口的字符频次。每次窗口滑动一格更新频次后比较s_count和p_count是否相等。相等就是答案之一。问题来了每次都比较整个长度26的数组复杂度是O(26·n)常数项比较大。26是常数所以理论上这依然是O(n)但面试中如果你直接说“我每次都比较整个数组”面试官通常会追问“能不能优化这个比较”。3.3 优化方案用一个计数器避免全量比较用一个整数matched记录当前窗口内有多少个字符的频次已经和p完全一致。当matched 26时说明26个字符的频次全部一致窗口就是一个异位词。维护规则右指针纳入新字符c时s_count[c]。如果p_count[c] 0并且p_count[c] s_count[c]说明字符c的频次正好对齐了matched。左指针移出旧字符时定长窗口必须同步左移如果p_count[旧字符] 0并且移动前s_count[旧字符] p_count[旧字符]说明这个字符本来是对齐的移出后就不对齐了matched--。这个技巧在“最小覆盖子串”题里也是核心学会一次到处用。3.4 标准解法代码def findAnagrams(s: str, p: str) - List[int]: if len(s) len(p): return [] p_count [0] * 26 s_count [0] * 26 for ch in p: p_count[ord(ch) - ord(a)] 1 res [] matched 0 n, m len(s), len(p) for right, ch in enumerate(s): idx ord(ch) - ord(a) s_count[idx] 1 if p_count[idx] 0 and s_count[idx] p_count[idx]: matched 1 # 窗口长度超过m时左指针需要右移 if right m: left_ch s[right - m] left_idx ord(left_ch) - ord(a) # 移动前如果这个字符是对齐的移动后就不对齐了 if p_count[left_idx] 0 and s_count[left_idx] p_count[left_idx]: matched - 1 s_count[left_idx] - 1 # 如果所有字符频次都对齐且窗口长度正好为m if matched 26 and right m - 1: res.append(right - m 1) return res这里有一点必须注意matched统计的是“有多少个字符的频次完全相等”所以即使p没有某个字符比如u只要窗口内u的频次不为0u永远不会被算进matched。最终只有matched 26才能说明整个窗口的每个字符频次都和p一致。不过你可能会想p只包含某些字符比如abc那窗口里出现了xmatched并不会因为x变成不对齐对吧确实不会但matched 26这个条件本身就要求所有26个字符频次都对齐而x出现在窗口里会导致s_count[x] p_count[x] 0它永远也到不了对齐状态所以matched永远凑不满26。这就是为什么这个方案是安全的。3.5 进一步简化更直观的等长滑动有一个更朴素的写法不用matched而是直接在遍历时维护一个定长窗口然后比较数组def findAnagrams(s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] p_count [0] * 26 window_count [0] * 26 for ch in p: p_count[ord(ch) - ord(a)] 1 res [] for i in range(n): # 加入右边新字符 window_count[ord(s[i]) - ord(a)] 1 # 移除左边旧字符保证窗口长度为m if i m: window_count[ord(s[i - m]) - ord(a)] - 1 # 窗口长度正好为m时检查 if i m - 1 and window_count p_count: res.append(i - m 1) return res这个写法看起来更直白每次比较长度26的数组。面试时如果对matched维护不够熟悉我建议你写这种直观版本把思路说清楚比追求最优常数更重要。等面试官追问“能不能优化”你再引出matched这个优化点反而能展示你的深度。3.6 第3题和第438题的对照表对比维度 第3题 第438题 窗口长度 动态变化 固定为len(p) 左指针移动时机 遇到重复字符 每前进一格都移动 左指针跳转规则 跳到上次重复位置1或保持 固定1 核心数据结构 哈希表记录最后位置 计数数组记录频次 记录答案时机 每次移动都更新最长长度 窗口长度合法时判断4. 从两道题提炼一套可复用的滑动窗口方法论很多刷题的人有个误区题目刷得多但都是“背代码”换个变体就不会了。如果你能停下来把第3题和第438题的共性抽出来碰到下一道滑窗题就会轻松很多。4.1 四步走牢牢记住这个思考框架我给自己总结的滑窗四步是初始化确定窗口用什么数据结构维护状态哈希表、数组、计数器初始化左右指针。扩展右边界右指针每走一步把新字符纳入窗口状态更新对应的计数或位置。收缩左边界根据题目条件决定左指针移动规则。可变窗口是“不满足条件就收缩”定长窗口是“每走一步就收缩”。更新答案答案的更新时机千变万化——有的在收缩后更新有的在每次移动后更新有的在恰好满足某个条件时更新。第3题是每步都更新第438题是窗口长度合法时判断。这套框架最难把握的是第3步和第4步的配合。我的建议是做题时先问自己三个问题窗口内维护的信息是什么是“有没有重复”还是“频次是否匹配”什么时候左指针必须移动是发现了冲突还是窗口超长什么时候更新答案是最值比较还是条件判断这三个问题的答案基本上就能确定代码骨架长什么样。4.2 可变窗口 vs 定长窗口写法差异的根源第3题和第438题最大的不同在于左指针的移动时机。可变窗口的核心是while循环收缩右指针不断加入字符一旦窗口状态非法有重复字符就持续收缩左指针直到合法。你在外面套一层while而不是写一个if这是为了防止收缩一次还不够的情况。第3题用if也能过是因为记录“上次出现位置”的做法直接确定了左指针应该跳到的位置不需要循环试探。但对很多其他滑窗题比如“无重复字符的最长子串”用Set实现那种写法就必须用while。面试时我建议你在第3题也用while加Set实现再讲一遍能让面试官看到你对两种模型的理解。定长窗口的核心是右指针移动一步左指针也必然移动一步保持窗口长度为固定值。所以在遍历循环里你既要做“纳入右边新字符”的操作也要做“移除左边旧字符”的操作。4.3 同一套模板能解决哪些衍生题把这两题吃透后下面这些题看起来就会非常亲切76. 最小覆盖子串可变窗口暴力滑到覆盖所有目标字符后收缩左边界找最短。567. 字符串的排列和438题一模一样只是要求返回布尔值。424. 替换后的最长重复字符可变窗口但不是用窗口内字符是否重复做条件而是用“窗口长度减最多出现字符数是否超过k”做收缩条件。1004. 最大连续1的个数 III和424题几乎同构把“最多可翻转0的个数”换成“最多允许的0的个数”。3. 无重复字符的最长子串本身就是最基础的模板。做这些题的时候你甚至可以先用第3题的模板跑一遍改改收缩条件再对照第438题的模板跑一遍改改答案更新逻辑。多对比几次滑动窗口就不再是“玄学”了。5. 刷题过程中的真实踩坑与面试表现建议这部分是我实际刷题、面试和帮别人review代码时攒下的经验常规题解里很少写。5.1 写代码时的常见错误第一左右指针的初始值不统一。我见过很多人把left初始化为0right初始化为1导致代码里到处都是right - left然后还要加1减1的补丁。建议统一写法left 0, right 0循环遍历right从0到len(s)-1窗口区间用左闭右开[left, right)或左闭右闭[left, right]都行但一旦选定就全程保持一致。第二字符频次数组的下标越界。438题里ord(ch) - ord(a)很好写但如果你在循环里重复写这个表达式很容易打错。建议循环开始前先把索引算出来存到变量里。第三忘记处理空串或len(s) len(p)的边界。第3题空串返回0第438题s长度小于p时直接返回空列表。这些边界条件在面试代码里一定要在一开始就处理掉否则跑测试用例时立刻露馅。第四把哈希表的“存在性判断”和“位置判断”混在一起。第3题里if ch in char_index这个判断不能单独使用必须加char_index[ch] left的窗口内判断。原因前面说过了字符可能出现在窗口外面不能因为“以前出现过”就收缩窗口。5.2 复杂度分析不能只背结论这两道题的时间复杂度都是O(n)空间复杂度O(1)固定字符集时或O(字符集大小。但面试官可能会追问“为什么是O(n)不是O(n·m)”关键在于每个字符最多被右指针访问一次被左指针访问一次。在右指针的循环里左指针虽然也会移动但总移动次数不会超过n次因为左指针永远不会回退。所以总操作次数是2n量级线性复杂度。这一点和第3题里“为什么左指针取max就能防止回退”是同一个道理。你把它讲清楚面试官心里会给你加分。5.3 面试时怎么展示思路手撕算法时面试官看的不仅是代码对不对还有你思考问题的方式。我建议按这个顺序讲先说暴力解告诉面试官“我可以先枚举所有子串但这样复杂度太高O(n²)以上”。这证明你能独立想出基础解法。再说滑动窗口的由来“我发现在遍历过程中很多信息是重复计算的相邻子串之间只差一个字符所以可以用两个指针维护一个窗口状态只增删一个字符。”然后给出代码骨架先写while right len(s)的外层循环再解释窗口状态怎么维护最后说明答案更新逻辑。最后补边界自动提出“如果len(s) len(p)直接返回空”、“空串返回0”等边界处理这比面试官问了你再补要强得多。5.4 刷完这两题后建议顺手做的小练习如果你今天刚把这篇文章里两题都手写过建议立刻做三件事用Set加while循环重新写一遍第3题感受一下“条件收缩”和“直接跳转”两种写法的差异。把438题的代码改造成567题“字符串的排列”只需要改返回值类型。尝试用第3题的思路去写76题“最小覆盖子串”你会发现除了收缩条件复杂一点整体框架完全没变。做完这三个练习你对滑动窗口的理解会比单独刷十道题还深。我个人在实际刷题过程中的体会是滑动窗口不是一个需要死记硬背的算法它更像是一种“复用已经扫过的信息”的思维方式。第3题和第438题之所以经典是因为它们恰好把这种思维用两种最典型的方式展现了出来——一个教你动态收缩左边界一个教你固定窗口滚动。把这两道题彻底吃透后面整个滑窗题族都会变得非常顺。最后再分享一个小技巧刷题时别急着看题解先用笔在纸上画出abba或cbaebabacd的窗口滑动过程每次脱手写代码前都先画一遍坚持一段时间你对指针的掌控感会有质的提升。