滑动窗口解力扣438：字母异位词与Python频次数组优化-北京尧图网络

先交代一下背景。力扣438题《找到字符串中所有字母异位词》是一道非常经典的滑动窗口入门题也是我在刷题前期花最多时间“悟”明白的一道题。很多教程把它归类为“中等难度”但在我看来这道题真正的价值不在于它本身的代码量而在于它把“窗口如何移动”“频次如何维护”“边界如何抠”这几个滑动窗口的核心问题一次性全部暴露出来了。如果你正在刷力扣用 Python 练题我建议把这道题放在你刷字符串类题目的第三四题的位置太早刷会被窗口更新逻辑劝退太晚刷又会觉得技巧太简单。恰到好处。这道题要解决的问题一句话概括就是给定两个字符串 s 和 p在 s 中找到所有 p 的字母异位词的起始索引。字母异位词指字母相同、排列不同的字符串例如 p abc那么 cba、bca、acb 都是它的字母异位词。题目本身不复杂但坏就坏在数据规模s 和 p 的长度最大可以到 3 万如果你真的一个位置截一段、排序再比较大概率直接超时。所以这道题考察的本质是对字符串连续片段做“状态维护”的能力也就是滑动窗口。我接下来会从题目本身到底在考什么开始一直讲到两种 Python 实现、diff 优化、模板提炼、以及我实际提交时踩过的坑。内容比较长但保证每一步都是可以直接照抄的。1. 先把题目吃透字母异位词到底要比较什么1.1 字母异位词的本质用一个比喻说清楚字母异位词anagram这个词听起来学术其实理解起来非常简单。你手头有两个箱子箱子里各有若干个球球的颜色种类和数量完全一样只是摆放的顺序可能不一样这两个箱子里的球集合就是“异位”的。字符串也一样abc 和 cba 就是字母异位词因为字母种类是 a、b、c数量各一个顺序不同不影响它们是同一种“内容”。但这里有个关键点字母异位词不是看顺序而是看频次表完全相等。字符串 s 中任何一个长度为 m 的子串只要它的“a-z 每个字母出现次数表”和 p 的频次表完全一致那这个子串就一定是 p 的某个排列。力扣题目给的示例很直观。s cbaebabacdp abc输出 [0, 6]。下标 0 开始的子串是 cba下标 6 开始的子串是 bac这两个都是 abc 的排列。注意题目要求返回所有满足条件的起始下标不是返回子串本身也不是返回数量这一点写代码的时候最容易忽略。1.2 输入输出边界条件决定你代码的稳定性题目还有一个非常重要的约束s 和 p 只包含小写英文字母。这个约束直接决定了我们可以用长度为 26 的数组来做频次统计而不是必须用字典。在面试场景里如果面试官出的变体包含大写字母、数字甚至 Unicode 字符那就要换用字典但那是后话。力扣原题的 26 个字母用数组是最优解。边界情况要提前想清楚如果 p 的长度大于 s 的长度那 s 中根本不可能存在长度与 p 相同的子串直接返回空列表。空字符串在题目里虽然可能出现但长度范围是 1 到 30000所以不用额外处理空串但自己写代码时如果想做成通用工具建议还是加上防御。返回的是“起始索引”第一个窗口的起始索引是 0不是 1。如果 s 和 p 完全相同例如 s abc, p abc答案是 [0]这个不能漏。边界条件不是算法核心但很多提交不通过都是死在边界上所以每次写题先花 10 秒把输入输出边界写在注释里比写完再去调试省时间得多。2. 从暴力到滑动窗口这个解法几乎是必然选择2.1 暴力排序法为什么在面试现场会被直接毙掉刚看到这道题时最直觉的想法是从 s 的第 0 位开始依次截取长度等于 m 的子串把子串排序把 p 排序如果排序后两个字符串相等就说明是字母异位词记录当前下标。这个思路的代码写出来可能不到 10 行看起来非常“合理”。但咱们算一笔账。设字符串 s 的长度是 np 的长度是 m。你一共要截取 n - m 1 个子串每个子串排序的复杂度是 O(m log m)总复杂度是 O((n - m 1) * m log m)。当 n 30000, m 15000 时这个计算量是亿级别的力扣肯定会给超时。就算不超时每轮切片还会产生新的字符串对象内存分配也是一笔开销。面试现场你把这个方案写出来面试官大概率会追问一句能不能不用排序因为排序本身就是一种“慢”的操作而“两个字符串是否是字母异位词”这个判断本质上不需要顺序参与。你只需要知道每个字母出现了几次顺序是无关紧要的。2.2 把异位词比较抽象成频次比较既然不需要顺序那很自然地就会想到用“哈希表”或者“数组桶”来统计字母出现次数。p 固定不变它的频次表只需要统计一次s 上的每个窗口我们要动态维护一个频次表。窗口向右滑动时右边新进入一个字母左边退出一个字母只把这两个字母的计数一加一减其他 24 个字母根本不用动。这就是滑动窗口的雏形。窗口的本质可以理解为一个长度固定的框你只关心框内字母的频次不关心框外的东西。每移动一格框内的变化只有两个字符所以理论上单步维护的复杂度是 O(1)。为什么不直接用字典因为 Python 字典虽然用起来方便但哈希查找本身有开销而且每次比较两个字典是否相等需要遍历字典的所有键时间复杂度是 O(k)k 是字典大小。数组的下标访问是 O(1)而且长度为 26 的数组比较起来就是一个内存块的比较在底层实现上非常快。题目限定小写字母数组是最贴合场景的数据结构。3. 基础版实现数组计数加全量比较能过但还有优化空间3.1 完整代码与逐行拆解我先把最直观、最容易理解的一版代码贴出来。这一版用两个长度为 26 的数组分别记录 p 的频次和当前窗口的频次每次滑动后直接比较两个数组是否相等。代码能过思路清楚适合作为第一版提交class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if m n: 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 if window_count p_count: res.append(i - m 1) return res这段代码的核心就是主循环里的三个动作加右、减左、比较。i 从 0 遍历到 n - 1每次把 s[i] 加入窗口。当 i 第一次大于等于 m 时说明窗口已经长到 m 个字符此时需要把窗口最左边的字符 s[i - m] 移出。这样窗口始终保持在长度 m。比较成功时为什么记录的是 i - m 1因为窗口从 i - m 1 开始到 i 结束正好是 m 个字符。比如 i 2, m 3窗口是 s[0] 到 s[2] 这三个字符起始下标就是 0等于 i - m 1 2 - 3 1 0。这个下标推导是滑动窗口题目里反复出现的细节务必要自己在本子上画一遍。3.2 “先加右、再减左”的顺序为什么不能反这个顺序问题非常隐蔽我第一次写的时候就没有细想觉得加减顺序无所谓。但认真推导一遍会发现顺序其实是固定的。窗口的物理含义是 s[i-m1] 到 s[i] 这一段。当循环执行到 i 时右边界 s[i] 应该先被纳入窗口统计否则窗口的右边界就不是 i 而是 i - 1。接下来再判断是否要删除 s[i - m]因为此时窗口长度已经到 m左边界是 i - m 1而上一个窗口的左边界是 i - m所以删除 s[i - m] 是让窗口从“s[i-m] 到 s[i-1]”平滑滑动到“s[i-m1] 到 s[i]”。如果反过来先删除、再添加会出错。举个具体例子。s abc, p abcm 3。当 i 2 时如果先删除 s[2 - 3] 也就是 s[-1]最后一个字符 c把窗口里本来还没加入的 c 扣掉逻辑就彻底乱了。只有先加 s[2] c再删 s[-1] c窗口频次才依然是 {a:1, b:1, c:1}与 p 匹配。这段代码整体上已经可以提交通过。但每轮执行window_count p_count时Python 实际会比较数组的 26 个元素虽然数组很短但 n 最大三万次总比较次数是 26n这是一个可以继续优化的常数项。4. 进阶优化用 diff 变量把比较成本从 O(26) 降到 O(1)4.1 全量比较的隐藏成本在哪里当你提交第三版代码时力扣给出的运行时间大概在 100 毫秒左右表现已经不错。但优化是无止境的(window_count p_count)这个比较语句看着轻巧实际底层要逐个比较数组的 26 个 int。大多数状态下窗口频次和 p 频次根本不同但 Python 不知道它必须全部比完才能下结论。有没有办法让判断“窗口是否匹配 p”变成 O(1) 的操作有那就是维护一个 diff 变量记录当前窗口的频次表与 p 的频次表之间“有多少个字母的计数不同”。当 diff 等于 0 时窗口就一定匹配 p。每轮滑动最多只有两个字符发生变化所以 diff 的更新也是 O(1)。4.2 diff 变量的设计与完整实现diff 的初始值怎么定一开始 window_count 全是 0p_count 有几个字母不为 0就有几个字母的计数不一致。比如 p abcp_count 中 a、b、c 都是 1window_count 中 a、b、c 都是 0有三个字母不一致diff 初始值为 3。然后初始化第一个窗口遍历 s[:m]把字符加入窗口。每加入一个字符需要判断它对 diff 的影响加入前这个字符的计数恰好等于 p_count 的目标值说明它本来处于“匹配”状态加入后会变成多一个匹配被破坏diff 加 1。加入后这个字符的计数恰好等于 p_count 的目标值说明它从不匹配变成了匹配diff 减 1。其他情况diff 不变。滑动的过程里右进一字符、左出一字符对每个字符用同样的规则更新 diff。完整代码如下class Solution: def findAnagrams(self, s: str, p: str) - List[int]: n, m len(s), len(p) if m n: return [] target [0] * 26 window [0] * 26 diff 0 # 统计 p 的频次并初始化 diff for ch in p: idx ord(ch) - 97 if target[idx] 0: diff 1 target[idx] 1 # 初始化第一个窗口 for ch in s[:m]: idx ord(ch) - 97 before window[idx] window[idx] 1 if window[idx] target[idx]: diff - 1 elif before target[idx]: diff 1 res [] if diff 0: res.append(0) # 滑动窗口 for i in range(m, n): # 右边界字符进入 idx ord(s[i]) - 97 before window[idx] window[idx] 1 if window[idx] target[idx]: diff - 1 elif before target[idx]: diff 1 # 左边界字符离开 idx ord(s[i - m]) - 97 before window[idx] window[idx] - 1 if window[idx] target[idx]: diff - 1 elif before target[idx]: diff 1 if diff 0: res.append(i - m 1) return res这套代码的核心是理解before target[idx]时匹配被破坏、window[idx] target[idx]时重新匹配这两个判断条件。我写一遍之后建议你结合具体例子手动走一遍比如 s abab, p ab跟着代码把每一步 window 数组和 diff 的值写出来比看十遍讲解都有用。4.3 数组比较、diff 计数和 Counter 三种方案的取舍实际写题时三种方案各有适用场景。我做了个对比表格供参考方案代码量单步复杂度是否建议力扣提交说明排序截取少O(m log m)不建议数据大时必超时只适合小规模验证双数组全量比较少O(26)可以最简单稳妥性能足够通过diff 计数中O(1)推荐常数最优秀但逻辑容易写错Counter 直接比较极少O(k)k 为字符种数不推荐竞赛用简洁但常数大笔试时可用我的建议是面试时先写出双数组全量比较版本保证正确性如果面试官追问优化再讲 diff 方案展示你理解窗口状态是可维护的。平时自己刷题则可以强制自己多写 diff 版本提升代码手感。5. 从 438 题提炼刷题模板一类滑动窗口题的通解5.1 定长窗口的通用代码骨架438 题属于“固定窗口长度”的滑动窗口。这类题有一个非常固定的骨架我整理出来之后刷后面 567、3、76 这些题时都直接复用这个思路def fixed_window_sliding(seq, window_size): n len(seq) if window_size n: return [] state init_state() # 根据题意维护的状态比如频次表 res [] # 先初始化第一个窗口 for i in range(window_size): add(state, seq[i]) if valid(state): res.append(0) # 窗口从 window_size 开始向右滑动 for right in range(window_size, n): add(state, seq[right]) # 右边界进入 remove(state, seq[right - window_size]) # 左边界离开 if valid(state): res.append(right - window_size 1) return res其中add、remove、valid三个函数的具体实现完全取决于题目。438 题里add 是在频次表上加一remove 是减一valid 是比较两个表是否相等或 diff 是否为零。理解了这三个函数和“滑动”这个过程你会突然发现所有定长窗口题都长得差不多。5.2 从 438 题变形出去的那些亲戚题力扣上与 438 关联最密切的一题是 567 题《字符串的排列》。它问的其实还是同一个东西s2 中是否存在 s1 的某个排列。只不过返回从“所有起始下标”变成了“是否存在”代码几乎一模一样只要在 diff 0 时提前返回 True 即可。我建议你把 438 和 567 放在同一天刷会有一种“白赚一题”的感觉。再往后是 76 题《最小覆盖子串》它是变长窗口的经典题思路依然可以用频次表和 diff 来维护但窗口不再固定长度而是右侧扩展、左侧不断收缩找到一个包含目标所有字符且长度最小的子串。这里 diff 的语义从“窗口与目标频次完全相等”变成了“窗口是否还缺少某些目标字符”。换句话说把 diff 的定义换成“当前窗口还需要多少个目标字符”就能复用 438 里维护 diff 的手感。还有 30 题《串联所有单词的子串》把单个字符比较变成单词比较本质上还是窗口只是“字符”换成了“单词”。如果你是系统刷题建议按这个顺序推进438 定长、567 定长变种、76 变长对比、30 的外层包装。每一题都和上一题只差一点点连续做下来滑动窗口的大梁就立起来了。6. 实战复盘提交记录、调试技巧与避坑清单6.1 我在力扣上踩过的三个典型坑第一个坑忘记处理 m n。这个错最蠢但出现率极高。p 比 s 长时没有任何子串能匹配如果你不返回空列表后面的代码大概率会访问不存在的切片位置或者直接返回一个奇怪的答案。所以所有滑动窗口题的第一步写长度判断几乎成了我的条件反射。第二个坑起始下标算错。窗口右边界在 i 时起始下标是 i - m 1。第一次没有加上这个 1导致输出整体偏移一位而且小的用例很难发现我把 s 改成 abab、p 改成 ab 的时候才发现 [0] 和 [1, 2] 的差别。第三个坑diff 的含义理解成“计数差的总和”。我之前看到网上有些写法把 diff 更新写成diff 2之类自己照着改时就写歪了。记住diff 在这里表示“字母频次不相等的字符种类数”不是“差的绝对值和”。用 p aaaa 这种重复字符多的用例去测如果 diff 维护错了结果一定会漏掉一些窗口。这三个坑我统一建议用下面这种“对拍”方法来自查import random from collections import Counter def brute_force(s, p): m len(p) cnt Counter(p) return [i for i in range(len(s) - m 1) if Counter(s[i:i m]) cnt] def test_solution(): for _ in range(20000): alphabet ab s .join(random.choice(alphabet) for _ in range(random.randint(1, 30))) p .join(random.choice(alphabet) for _ in range(random.randint(1, 15))) a brute_force(s, p) b Solution().findAnagrams(s, p) if a ! b: print(不匹配, s, p, 暴力结果, a, 算法结果, b) return print(全部通过)这个脚本的思路是暴力解法正确但慢滑动窗口快但容易错随机生成大量小规模用例将两者结果对比一旦不一致就能立刻定位到具体字符串组合。我在本地跑几万组随机数据比自己反复提交力扣试错高效得多强烈建议你也搭一个。6.2 几个提升 Python 提交性能的小技巧如果你追求力扣榜单上的漂亮时间有几个细节可以改。把ord(a)这种重复计算提取为常量BASE 97循环里直接ord(ch) - BASE。把len(s)、len(p)提前存成局部变量避免每次循环重新取。把ord这种高频调用放在循环外引用虽然 Python 的局部变量查找已经很快但省一点是一点。我更想强调的是另一个维度代码可读性。LeetCode 刷题不是只有通过就行你所写的代码就是你和面试官沟通的语言。在函数开头写上边界处理注释在 diff 判断逻辑处写明“diff 表示不匹配的字符种类数”这些注释在面试时非常加分。我见过太多人代码全对但讲不出每一行的意图最后被面试官怀疑是背题的。所以平时练习就要养成边说边写的习惯。6.3 这道题在实际工程里能用来做什么聊点算法题之外的东西。字母异位词匹配这个模型本质上是一个“内容相同但顺序不同”的快速检测器。在文本分析场景里比如判断两个文档片段是否只是打乱了词语顺序或者在一个长日志流里寻找某组特定字段的任意排列出现的位置都可以抽象成这个模型。做实时数据流处理的时候我们常会遇到“固定长度时间窗口内统计事件类型频次”的需求这和这道题的结构几乎一致事件类型对应字母窗口长度对应 m每次新事件进来、旧事件出去维护一个计数数组然后判断是否满足某个预设条件。这个模式也叫“基于滑动窗口的流式聚合”是大数据领域特别基础的手段。所以刷这道题积累的经验并不只在面试里有用。我个人刷了这么多题最大的体会是像 438 这种题真正核心的收获不是记住“如果窗口频次等于 p 的频次就记录下标”这个结论而是理解“窗口状态可以被一个变量实时维护”这种思维。你从排序暴力到数组比较再到 diff 维护每一次优化都是对“状态”这个概念的重新理解。如果你能把 diff 的含义和更新规则用自己的话讲给一个没写过代码的朋友听并且他能听明白那这道题就真正过关了。最后再分享一个实用小技巧这道题的 diff 版本我至今没默写过一遍不出的建议你也把代码手写三遍第一遍照着抄第二遍关掉参考凭记忆写第三遍顺便在注释里把每一步的 diff 变化标注出来。三遍之后你会发现自己对滑动窗口的掌控感上了一个台阶。

滑动窗口解力扣438：字母异位词与Python频次数组优化

相关推荐

易语言字节集从入门到实战：内存模型、协议解析与性能优化

生成式引擎优化服务商横向测评｜长沙4家服务商优势与适用场景

海外仓和直邮怎么选？转仓决策表

更多资讯

ST语言位操作指令WAND/WOR/WXOR：设备联锁逻辑的掩码化改造

BeagleY-AI实战：Python开发与AI模型部署全指南

ESP8285+MQTT实现电机控制器轻量级物联网接入

OCP V3 48V 5.5kW PSU设计规范深度解析

智能制造导论怎么读？四遍阅读法+核心概念解析

PJ85718DM+PIC18F4680工业温控方案：热电偶高精度采集与抗干扰设计

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？