做内容平台时碰到过一个特别现实的需求用户帖子里如果混进了敏感品牌词的字母重排写法比如把“apple”写成“paple”“appel”系统得能自动识别出来。这种“组成字母完全相同、只是顺序不同”的字符串就是字母异位词。正则表达式遇到这种问题基本报废因为你不可能把所有排列都穷举一遍。我当时花了点时间把异位词检测彻底做了一次专项研究LeetCode 438题“找到字符串中所有字母异位词”正好是这个问题最经典的抽象给定字符串s和p找出s中所有p的字母异位词的起始下标。这篇文章的完整解题思路既适合准备算法面试的同学也适合工作中要做文本匹配、又受够正则限制的工程师。1. 从“暴力排序”到“频次计数”异位词比较的两种基础姿势1.1 最直觉的解法把子串排序后在比较刚拿到438这道题大部分人的第一反应是排序。要判断s里某个子串是不是p的异位词最粗暴的办法就是把这个子串截出来、排序再和排序后的p做逐位比较。假设s cbaebabacdp abc那么s的前三个字符cba排序后是abc和p排序后一模一样于是位置0就是一个答案。接着看ba e截bae排序后是abe不等于abc排除。这样逐个位置扫下去就能拿到所有结果。这个思路本身完全正确但如果你真按这个写法交上去大概率得到一个TLE超时。原因很简单排序是有代价的。每次截取一个长度m的子串排序一次就是O(m log m)而s里大约有n个可能的起点整体复杂度是O(n * m log m)。当s和p都是10的4次方量级时这个数字会膨胀到10的8次方到10的9次方之间单次循环都够呛更别说跑在判题服务器上。1.2 复杂度算一笔账为什么排序解法必死再把账算细一点。假设n是s的长度m是p的长度我们用最朴素的排序法外层枚举s中每个可能的起点数量是n - m 1近似n。每个起点要做一次 slice 切片长度为m。对长度为m的切片排序一般语言里排序是O(m log m)。排序后和排序好的p逐位比较一次O(m)。所以总时间是(n - m 1) * (m log m m)。如果n和m都接近10的四次方那就是大约10的4次方乘以10的四次方乘以14算下来是10的9次方级别。即便有常数优化这也不是一个能在LeetCode标准时间限制里跑完的计算量。这也是面试时面试官希望看到的分析过程——不是“我觉得它会超时”而是“排序解法的时间复杂度是O(n*m log m)在数据量大了以后不可行”。1.3 频次计数不排序也能比较两个字符串进一步想两个字符串互为异位词的本质是什么是字母组成完全相同和顺序没有关系。既然和顺序无关那就不需要排序。用长度为26的数组记录字符串中每个字母出现的次数然后比较两个频次数组是否相同就能一次性判断异位词关系。还是cba和abc把它们都统计成频次数组cba → a:1b:1c:1abc → a:1b:1c:1两个数组完全一致所以互为异位词。这个思路已经比排序好太多单次比较从O(m log m)降到了O(26)因为数组长度固定是26逐位比较也就26次。但问题在于如果你对s的每一个起点都重新统计一次m长度的子串频次每次统计还是O(m)总复杂度会退化成O(n*m)跟“排序后比较”比没本质提升只是常数小了。真正需要的是一种能“复用前一个窗口统计结果”的方法。上一个窗口整体右移一格窗口内只减少左边一个字符、增加右边一个字符其他25个字符的频次完全没变那为什么要把整个窗口的频次重新算一遍把这个复用逻辑做好就是滑动窗口。2. 固定窗口滑动438题最稳的解法与实现2.1 一次遍历内的窗口维护用right和left的固定关系控制长度既然p的长度是m那么在s里滑动的窗口长度也始终是m这是固定窗口。很多讲解用left和right两个指针分别代表窗口两端但其实因为这个窗口长度恒定right每前进一步left也固定前进一步两者永远保持right - left 1 m 的关系。这个恒定关系是解题的定心丸。遍历s时把right当作遍历下标每处理一个新的字符就把这个字符的频次加进窗口。同时检查一下窗口是不是已经超出长度如果right已经走到m及以后说明窗口左端已经越过了第一个位置需要把离开窗口的最左侧字符频次减掉以维持窗口长度始终是m。窗口更新完成后窗口内部恰好就是当前“slide”到的m长度子串。这时把窗口频次数组和目标频次数组直接比对如果相同窗口起点就是right - m 1。这个起点公式是整个代码里最值得注意的位置很多初学者会在这里用错下标。2.2 代码实现Python版固定窗口直接上代码这个版本是我刷438题时最终保留的版本最稳也最好解释。from typing import List def find_anagrams(s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] need [0] * 26 for ch in p: need[ord(ch) - ord(a)] 1 window [0] * 26 res [] for right in range(n): # 右侧新字符进入窗口 window[ord(s[right]) - ord(a)] 1 # 窗口长度一旦超过m左侧字符离开窗口 if right m: window[ord(s[right - m]) - ord(a)] - 1 # 只有窗口长度刚好为m时才可能是答案 if right m - 1 and window need: res.append(right - m 1) return res这里循环里有两个关键判断right m 时窗口已经完整覆盖了至少两段长度为m的子串此时需要把离开窗口的字符频次减掉保证窗口频次数组始终只描述当前长度为m的窗口。right m - 1 时窗口长度才第一次达到m。如果没有这个判断在窗口还没填满的时候就比较window和need会得到错误结果。2.3 窗口起点为什么是right - m 1很多人在这一步栽过。假设m 3right 2那么当前窗口覆盖的是s[0]、s[1]、s[2]起点是0而right - m 1 2 - 3 1 0正好对得上。当right 3时窗口覆盖s[1]、s[2]、s[3]起点是1而3 - 3 1 1。所以验算一下就能确认这个公式在任何位置都正确。如果错误地写成right - m那所有的起始下标都会整体左移一位LeetCode判题会直接报错。这种错误特别隐蔽因为小规模样例可能侥幸通过但边界位置一定翻车。2.4 实测性能经验直接数组比较并不慢这一段是我自己的真实体感。有的解法为了优化会用一个match计数变量去记录当前窗口与目标频次有多少个字符达到一致从而避免每次比较window和need两个数组。理论上match计数可以做到O(1)更新但这只在需要动态收缩窗口的题目里才是必需品。在438这种固定窗口题里直接写window need反而是最省心的方案。Python列表的相等比较在底层由C实现长度只有26逐位比较的开销非常小。相比之下自己用Python代码维护match变量每一步都要写几行if判断和递增递减执行效率不见得比C层面的数组比较快出错概率还更大。这就引出一个重要的经验不要为了优化而优化。先确认当前算法的瓶颈在哪再决定要不要引入更复杂的状态维护。438题固定窗口版本里瓶颈根本不在比较两个数组上而在于必须遍历一次s这是无法避免的下限。3. 进化的关键matched匹配计数法及其在动态窗口里的地位3.1 固定窗口的局限窗口长度一旦动态变化就麻烦了如果只做438题固定窗口加数组直接比较确实够用。但滑动窗口的考察远不止固定长度这一种LeetCode 76题“最小覆盖子串”就是一个典型反例窗口长度不固定需要动态伸缩。此时“窗口频次数组是否等于目标频次数组”这种布尔判断就不好用了因为你不知道窗口多长才叫“合法”你得知道“当前窗口距离完全覆盖目标还差多少”。这就是matched匹配计数法登场的场景。它的想法很简单不一次性比较两个数组而是维护一个整数matched表示当前窗口里有多少个字符的频次已经和目标need的频次完全一致。当matched等于need中非零频次的字符数时说明当前窗口完整覆盖了目标。3.2 required和matched的定义别把没用的字符算进去这里有一个容易搞错的细节。need数组里很多字符的频次是0这些字符根本不出现在p中窗口里有没有它们、有多少个都不影响“窗口是否覆盖p”的判定。如果把所有26个字符都统计到达标数量那matched从第一秒开始就混入了大量无意义字符永远无法用matched 26作为判定条件。所以要单独算一个required它等于need数组中值大于0的元素个数也就是p中真正出现过的不同字符数量。438题里p若为abcrequired就是3只有a、b、c三个字符的频次都达到need要求matched才等于3。3.3 加入字符和移出字符时matched的四种变化情况维护matched最tricky的地方在于窗口移动时每一次频次变化都会同时影响两个字符右侧新加入的字符和左侧离开的字符。对每个变化都要在“加入前是否达标”和“加入后是否达标”之间做一个判断。以加入字符c为例假设频次数组have、需求数组need加入前have[c]等于need[c]加入后就不等了matched要减1。加入前have[c]不等于need[c]加入后正好等于need[c]matched要加1。加入前后都不等或者加入后依然不等于need[c]matched不变。加入前不等于、加入后也不等于matched保持不变。所以标准写法是先看更新前的旧值再更新频次最后看更新后的新值按两种情况增减matched。移出字符时同理只是方向相反先判断旧值是否达标再减频次再判断新值是否达标。代码里最容易犯的错是“先更新频次再看旧值”这样旧值已经丢了判断必然出错。我自己第一次写76题时就栽在这个顺序上调了半小时才意识到是判断顺序问题。3.4 用matched计数法重写438题下面是把matched计数法套用到438题的完整写法。虽然对固定窗口来说这种写法属于“杀鸡用牛刀”但它是通往更复杂滑动窗口题的唯一路径值得完整理解。from typing import List def find_anagrams(s: str, p: str) - List[int]: n, m len(s), len(p) if n m: return [] need [0] * 26 for ch in p: need[ord(ch) - 97] 1 required sum(1 for cnt in need if cnt 0) have [0] * 26 matched 0 res [] for right in range(n): # 右侧字符进入窗口先判断旧值状态 idx ord(s[right]) - 97 if have[idx] need[idx]: matched - 1 have[idx] 1 if have[idx] need[idx]: matched 1 # 左侧字符离开窗口 left right - m if left 0: idx ord(s[left]) - 97 if have[idx] need[idx]: matched - 1 have[idx] - 1 if have[idx] need[idx]: matched 1 if matched required: res.append(right - m 1) return res验证一下逻辑假设need[0]2当前have[0]2matched中a字符处于达标态。此时新字符a进入窗口have[0]从2变成3新值不再等于needmatched减1描述的就变成了“a字符从达标变为不达标”。如果当前have[0]1、need[0]2新字符a进入后have[0]变成2matched加1描述“a字符从不达标变为达标”。移出字符时完全镜像。这个版本里有一个典型的“动态窗口模板雏形”右侧扩展、左侧收缩、matched同步更新、最后按条件判断是否合法。438题因为有固定窗口长度left必须跟着right同步移动到76题时left的移动就会变成“只要当前窗口合法就尝试收缩看看能不能找到更小合法窗口”。4. 四个高频坑位索引、字符集、边界和所谓“优化”4.1 right和left谁先动顺序错了窗口长度就乱了固定窗口版本里有的同学喜欢把left作为独立变量维护然后写“right进一格、window更新、left进一格、window更新”这种双更新。这个写法没什么毛病但一定要保证顺序一致要么先加右再减左要么先减左再加右不能在代码的不同分支里混用顺序。否则在某些循环分支下窗口长度会变成m1或者m-1频次数组描述的就是一个“假窗口”。我个人习惯是始终先处理右侧新字符再处理左侧离开字符因为窗口的定义是左闭右闭先加右侧再减左侧窗口语义最清晰。给读者的建议是固定用一种顺序不要临场换。4.2 字符集不只26个小写字母怎么办LeetCode里438题限定了s和p仅包含小写字母所以频次数组用26就能通过。但真实业务场景下文本可能包含大写字母、数字、空格、甚至Unicode字符。面试官也可能在follow-up里故意问如果字符集变成ASCII全集怎么办。这时候最简单的处理是把频次数组从26扩到128对应ASCII码范围。如果是更大的Unicode字符集数组扩到几万就不现实了需要用哈希表比如Python的CounterJava的HashMap。主要改动点有两个ord(ch) - ord(a) 换成 ord(ch)因为ord直接就是0到127need中非零字符的统计换成遍历哈希表key而不是遍历固定长度数组。4.3 空字符串和p比s长的边界代码开头必须处理p为空串的情况。如果p是空串need数组全为0required就是0matched一开始就等于required无论s怎么滑都会被判定为合法窗口。更关键的是m0时窗口长度为0right - m 1会变成right 1答案是错的。所以实战中我一律先判断这个边界p为空直接返回空列表不参与主逻辑。另一种边界是p长度大于s。窗口长度为ms总长度nm窗口根本不可能建立此时直接返回空列表。这两个边界条件能挡住大部分隐藏的index错误。4.4 别被“优化”带偏部分场景下简洁代码跑得更快第三章节里提到了matched计数法在动态窗口中的必要性但在固定窗口题里它并不是性能最优解。我实测过官方数据量下Python的“数组直接比较”版本运行时间比“手工维护matched”版本短原因是数组相等比较在C层面批量执行而matched维护需要逐字符执行Python级别的条件判断。所以选择实现方案时要先判断这道题的窗口长度是否固定。窗口固定时用数组直接比较代码短、语义清晰、性能也不差窗口动态变化时才有必要引入matched计数法。这也是面试时可以说给面试官听的“性能决策思路”比直接套路化甩出一个模板加分得多。5. 变体训练把438的模板迁移到567、76、3题5.1 567题找排列把结果集改成布尔值LeetCode 567题要求判断s2是否包含s1的某个排列。它和438题几乎一模一样唯一的区别是438题要求返回所有起始下标567题只需要返回是否存在。做法可以直接沿用固定窗口版本窗口长度固定为s1的长度遍历s2时一旦window need就返回True遍历完还没有就返回False。从这个角度说567题就是438题的简化版。我的建议是先做438再做567两个题一起刷能明显感受到“同一个模板换一层壳”的感觉。5.2 76题最小覆盖子串动态收缩窗口的完整实现76题“最小覆盖子串”才是matched计数法真正的主场。给定字符串s和t在s中找出包含t所有字符的最小子串窗口长度不固定。核心思路是用right扩展窗口直到matched required说明当前窗口已经覆盖了t这时尝试用left收缩窗口左端每收缩一步都检查窗口是否仍然覆盖t如果仍然覆盖就更新最小长度。重复收缩直到窗口无法覆盖t再继续用right扩展。因为窗口长度随时在变不能像438那样用right - m固定计算窗口起点left需要作为独立指针保存。完整示例如下def min_window(s: str, t: str) - str: if len(s) len(t): return need [0] * 128 for ch in t: need[ord(ch)] 1 required sum(1 for cnt in need if cnt 0) have [0] * 128 matched 0 left 0 min_len float(inf) start 0 for right in range(len(s)): idx ord(s[right]) if have[idx] need[idx]: matched - 1 have[idx] 1 if have[idx] need[idx]: matched 1 while matched required: if right - left 1 min_len: min_len right - left 1 start left idx ord(s[left]) if have[idx] need[idx]: matched - 1 have[idx] - 1 if have[idx] need[idx]: matched 1 left 1 return s[start:start min_len] if min_len ! float(inf) else 这段代码里最值得研究的是while matched required的收缩循环。它和438题的if left 0有本质区别438是窗口长度定死left只能跟着right同步走76是窗口合法后持续收缩直到非法为止。两者分别对应固定窗口和动态窗口两种模式理解了它们的差异才算真正掌握了滑动窗口的判断逻辑。5.3 3题最长无重复字符子串另一类“窗口”题目3题“无重复字符的最长子串”和438、76的套路不太一样但它也是滑动窗口思想的典型应用。这里不再需要need数组而是维护窗口内每个字符的出现次数只要窗口中所有字符频次都不超过1窗口就是合法的可以尝试记录最大长度。一旦某个字符出现两次就用left不断收缩窗口直到该字符频次降回1。因为不需要和目标字符串比较这道题的维护逻辑反而更简单right扩展时把频次加一发现频次超过1就收缩left然后更新答案。建议把3题和438、76放在一起刷能彻底打开“滑动窗口”这个解题框架的视野。5.4 四道题的横向对比固定窗口与动态窗口的判断依据把这几道题放在同一张表格里对比整个滑动窗口的家族关系会非常清楚。题目窗口长度判断条件输出核心技巧438 找到字符串所有字母异位词固定为mwindow need所有起始下标数组直接比较567 字符串的排列固定为mwindow need是否存在布尔结果76 最小覆盖子串动态matched required后收缩最小子串matched计数法3 无重复字符的最长子串动态窗口内字符频次不超1最大长度频次加left收缩这张表的意思是先看窗口长度固定不固定。固定优先用数组直接比较代码最省事不固定再用matched计数法并单独维护left指针。做题的时候先问自己这两个问题比盲目套模板靠谱得多。我个人刷完这四道题后最深的体会是滑动窗口难点不是算法本身而是状态更新的时序。窗口扩一个字符、缩一个字符频次数组和matched都在变化任何一处“先更新再判断旧值”都会导致状态污染。刷438题时把固定窗口版本和matched版本各写一遍再去做76题会顺畅很多反过来硬刷76题很容易被matached维护细节绕晕。倒不如花半小时把438的两种写法吃透把时序逻辑练成肌肉记忆。