企业官网建设流程全解析

LeetCode 438 找到字符串中所有字母异位词（Python 固定滑动窗口+字符计数解法）

刷题标签：#滑动窗口 #字符计数 #字符串 #中等难度
题目链接：LeetCode 438

一、题目描述

给定两个字符串s和p，找到s中所有p的字母异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

名词解释：字母异位词

两个字符串字符种类、每个字符出现次数完全一致，仅字符排列顺序不同，互为字母异位词。
例：ab与ba、abc与cba都是异位词。

示例

示例 1

输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。

示例 2

输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引 0 → "ab"、索引 1 → "ba"、索引 2 → "ab"，均为 "ab" 的异位词。

提示

• 0 <= s.length <= 5 * 10^4
• s由英文字母、数字、符号和空格组成（本题仅考虑小写英文字母）
• 异位词一定长度相等，因此只需在s中截取长度等于len(p)的连续子串判断。

二、前置核心概念

1. 固定大小滑动窗口

滑动窗口是字符串/数组刷题常用技巧，分为变长窗口和定长窗口：

• 本题使用固定窗口：窗口宽度 = 短字符串p的长度，窗口只能整体向右逐格平移，大小永远不变。
• 比喻：把长字符串s看作一条长廊，窗户宽度固定，每次只向右挪一格，逐段检查窗口内内容。

2. 字符计数数组

题目仅包含 26 个小写英文字母，我们用长度为 26 的数组统计字符出现次数：

• 映射规则：字母下标 = ord(字符) - ord('a')，实现a→0、b→1 ... z→25
• 优势：字符查找、计数修改时间复杂度为O(1)O(1)O(1)，效率远高于字符串排序。

三、解题思路整体分析

思路1：暴力排序（仅入门理解，大数据超时）

1. 先将模板字符串p排序，作为比对标准；
2. 在s中截取所有长度等于len(p)的连续子串，逐个排序；
3. 若子串排序后与p排序结果一致，则记录子串起始下标。

缺点：每次截取+排序，时间复杂度高，字符串较长时会超时，仅适合理解题意。

思路2：滑动窗口 + 字符计数（最优解，面试/刷题首选）

1. 定义两个计数数组：
   • 基准数组：统计模板p的字符出现次数（标准答案，全程不修改）；
   • 窗口数组：统计s当前滑动窗口内的字符出现次数（窗口移动时动态更新）。
2. 初始化首个窗口：统计s前len(p)个字符，对比两个数组，匹配则记录下标。
3. 窗口逐格右移：
   • 窗口左侧字符滑出：窗口数组对应位置计数-1；
   • 窗口右侧新字符滑入：窗口数组对应位置计数+1；
4. 每次移动后对比两个计数数组，匹配则记录当前窗口起始下标。

优点：仅遍历一次字符串，时间复杂度O(n)O(n)O(n)，可通过所有测试用例。

四、解法一：暴力排序法（入门版）

完整代码

classSolution(object):deffindAnagrams(self,s,p):res=[]len_s=len(s)len_p=len(p)# 边界：模板更长，直接返回空iflen_p>len_s:returnres# 将p排序，作为比对标准p_sort=sorted(p)# 遍历所有合法起始位置foriinrange(len_s-len_p+1):# 截取当前窗口子串并排序sub_str=s[i:i+len_p]ifsorted(sub_str)==p_sort:res.append(i)returnres

代码解读

1. 边界判断：如果p长度大于s，不存在异位词，直接返回空列表；
2. 预处理：对p排序，异位词排序后结果完全相同；
3. 遍历所有合法窗口起点，截取子串排序后比对，匹配则记录下标。

优缺点

• ✅ 逻辑简单，新手易理解；
• ❌ 排序操作耗时，数据量大时超时，不适合工程使用。

五、解法二：滑动窗口 + 字符计数（最优解）

5.1 完整可运行代码

该版本为最终修正版，规避了数组职责混淆、循环嵌套、下标错误等常见坑点：

classSolution(object):deffindAnagrams(self,s,p):""" :type s: str :type p: str :rtype: List[int] """res=[]len_s=len(s)len_p=len(p)# 边界判断：p比s长，无答案iflen_p>len_s:returnres# 两个计数数组：win存模板p(基准，固定不变)，ts存s的滑动窗口(动态更新)win=[0]*26ts=[0]*26# 第一步：初始化统计 p 和 s 的第一个窗口foriinrange(len_p):# 统计模板 p 的字符次数char_p=p[i]index=ord(char_p)-ord("a")win[index]+=1# 统计 s 第一个窗口的字符次数char_s=s[i]index1=ord(char_s)-ord("a")ts[index1]+=1# 检查第一个窗口是否匹配ifwin==ts:res.append(0)# 第二步：窗口持续向右滑动foriinrange(len_p,len_s):# 1. 左侧字符滑出窗口，窗口计数-1char_left=s[i-len_p]index2=ord(char_left)-ord("a")ts[index2]-=1# 2. 右侧新字符滑入窗口，窗口计数+1char_right=s[i]index3=ord(char_right)-ord("a")ts[index3]+=1# 两数组完全相等，说明当前窗口是异位词ifwin==ts:res.append(i-len_p+1)returnres

5.2 逐行代码详解

1. 基础变量与边界判断

res=[]len_s=len(s)len_p=len(p)iflen_p>len_s:returnres

• res：结果列表，存储所有符合条件的窗口起始下标；
• len_s / len_p：分别记录两个字符串长度；
• 边界兜底：若模板p更长，直接返回空列表。

2. 初始化26位字符计数数组

win=[0]*26ts=[0]*26

• [0] * 26：生成长度为26、初始值全为0的数组，对应a~z26个小写字母；
• win：基准数组，仅统计模板p，初始化后全程不修改；
• ts：窗口数组，统计s中当前窗口的字符，窗口移动时动态修改。

3. 初始化首个窗口

foriinrange(len_p):char_p=p[i]index=ord(char_p)-ord("a")win[index]+=1char_s=s[i]index1=ord(char_s)-ord("a")ts[index1]+=1

• 循环次数 = 窗口宽度len(p)，一次性完成模板p和s首个窗口的字符统计；
• ord(字符) - ord("a")：核心映射公式，将字母转为 0~25 的数组下标；
• 数组[下标] += 1：对应字符出现次数 +1。

4. 检查首个窗口

ifwin==ts:res.append(0)

• 两个计数数组完全一致 → 首个窗口是异位词，记录起始下标0；
• 该判断必须放在循环外，避免逐个统计字符时重复判断。

5. 窗口滑动核心逻辑

foriinrange(len_p,len_s):# 左侧字符滑出char_left=s[i-len_p]index2=ord(char_left)-ord("a")ts[index2]-=1# 右侧字符滑入char_right=s[i]index3=ord(char_right)-ord("a")ts[index3]+=1ifwin==ts:res.append(i-len_p+1)

• 循环范围：从len_p开始遍历，逐个处理新进入窗口的字符；
• 固定公式1：i - len_p→ 被窗口挤出的左侧字符下标；
• 固定公式2：i - len_p + 1→ 当前窗口的起始下标；
• 规则：窗口移动只修改窗口数组ts，基准数组win保持不变。

6. 返回结果

returnres

遍历完成后，返回所有合法下标。

5.3 实战流程演示（示例：s = "abab",p = "ab"）

字符串下标：s[0]=a、s[1]=b、s[2]=a、s[3]=b，窗口宽度len_p=2

1. 初始化阶段

   • win = [1,1,0,...]（统计p=ab）；
   • ts = [1,1,0,...]（统计s首个窗口ab）；
   • 数组匹配，res = [0]。

2. 窗口滑动 i=2（新字符 a）

   • 挤出左侧s[0]=a→ts[0] -= 1；
   • 纳入新字符s[2]=a→ts[0] += 1；
   • 数组仍匹配，起始下标1，res = [0,1]。

3. 窗口滑动 i=3（新字符 b）

   • 挤出左侧s[1]=b→ts[1] -= 1；
   • 纳入新字符s[3]=b→ts[1] += 1；
   • 数组仍匹配，起始下标2，res = [0,1,2]。

4. 最终输出：[0,1,2]，与题目答案一致。

六、复杂度分析

1. 暴力排序法

• 时间复杂度：O(N⋅Klog⁡K)O(N \cdot K\log K)O(N⋅KlogK)，NNN为s长度，KKK为p长度（每次排序耗时Klog⁡KK\log KKlogK）；
• 空间复杂度：O(K)O(K)O(K)，存储排序后的字符串。

2. 滑动窗口+字符计数（最优解）

• 时间复杂度：O(N)O(N)O(N)，仅遍历一次字符串，26位数组对比为常数操作；
• 空间复杂度：O(1)O(1)O(1)，两个固定长度为26的数组，空间不随输入变化。

七、刷题高频踩坑总结（新手必看）

结合调试过程中遇到的问题，整理最容易出错的5个点：

1. 数组职责混淆（最高发错误）

   • 基准数组（存p）是标准答案，初始化后绝对不能修改；
   • 窗口移动时，仅能修改窗口计数数组，修改基准数组会导致全部判断失效。

2. 判断逻辑嵌套错误

   • 窗口初始化的for循环内，不要加入数组比对逻辑；
   • 必须等整个窗口统计完成后，再执行一次比对，否则会重复记录下标。

3. 列表 append 语法错误

   • 正确：res.append(数值)（圆括号）；
   • 错误：res.append[数值]（方括号是取值，不能调用方法）。

4. 窗口下标公式记错

   • 滑出字符下标：i - len_p；
   • 窗口起始下标：i - len_p + 1；
     下标计算错误会导致取到非法字符，程序报错。

5. 字符来源错误
   滑动窗口的所有进出字符都来自长字符串s，不要错误从模板p中取值。

八、总结与同类题型推荐

知识点总结

1. 本题核心组合：固定滑动窗口 + 字符计数数组，是字符串高频解题模板；
2. 26位字母计数数组是小写字母类题目的常用优化手段，替代排序可大幅提升效率；
3. 定长滑动窗口通用流程：初始化首窗口 → 逐格滑动窗口（左出、右入）→ 校验结果。

同类刷题推荐

1. LeetCode 3 无重复字符的最长子串（变长滑动窗口）
2. LeetCode 567 字符串的排列（异位词变种，同解法）
3. LeetCode 209 长度最小的子数组（定长/变长滑动窗口综合练习）