找到字符串中所有字母异位词 图解题解
p 的所有异位词藏在 s 的哪些位置？一块等宽纸片从头滑到尾，边滑边比计数。
像用一块和 p 等宽的透明纸片在 s 上从左滑到右：纸片宽度固定，每往右移一格就纳入右边新字母、丢掉左边旧字母，字母计数 O(1) 更新。只要纸片里每个字母的数量和 p 的字母计数完全吻合，不管顺序怎样，起点就是一个答案。滑一遍，全部找齐。
这道题到底在问什么
- s
- "abba"
- p
- "ab"
- 输出
- [0, 2]
最优解：一步一步想明白
- 3每个起点都切出长 k 的子串、排好序和 p 比，能做，但每个窗口都重头排序，重复劳动太多。
- 4窗口长度固定等于 len(p)。先数出 p 的字母计数，再让窗口在 s 上滑：每右移一格，右边新进一个字符、左边挤出一个字符，计数 O(1) 更新。窗口计数和 p 计数一致，起点就是答案。计数相等就是异位词（顺序无所谓），所以根本不用排序。
- 5p 计数 a=1 b=1, 窗口长 2先数 p="ab"：a 一个、b 一个。窗口固定 2 格，将从最左滑到最右，每停一处就比一次计数。
- 6窗口 "a", 计数 a=1先把前 k=2 个字符装进首窗口。第一个吃进 a，计数 a=1，窗口还差一格、先不比。
- 7计数 a=1 b=1第一个窗口 "ab"，计数和 p 一模一样——是异位词！记下起点 0。ans=[0]。
- 8进 s[2]=b, 出 s[0]=a窗口整体右移一格：右端吃进 s[2]=b，左端挤出 s[0]=a。这就是定长滑窗的核心——一进一出，不用重数。现在窗口是 "bb"。
- 9计数 a=0 b=2 ≠ p"bb" 的计数是 a 零个、b 两个，b 多了一个、a 少了一个，和 p 对不上——不是异位词，跳过不记录。这就是反例：计数不等就直接放过，窗口照样往右挤。
- 10进 s[3]=a, 出 s[1]=b继续右移：右端吃进 s[3]=a，左端挤出 s[1]=b。同样只改了两个计数。窗口变成 "ba"。
- 11计数 a=1 b=1 等于 p"ba" 计数 a 一个 b 一个，又和 p 相等——是异位词！记下起点 2。顺序虽和 p 不同，但计数相等就算数。ans=[0, 2]。
- 12窗口从 [1,2] 滑到 [2,3]：减旧 b、加新 a把这关键一步放慢看：窗口右移，先把离开的 s[1]=b 减一，再把新进的 s[3]=a 加一。其余 24 个字母的计数纹丝不动——这就是滑窗每步只花 O(1) 的原因。
- 13答案 = [0, 2]窗口右端到头，再也滑不动了。一路收集到的起点是 [0, 2]，就是答案。
- 16凡是「固定长度子串/子数组，问满足某条件的有几处」都是这个套路：窗口右滑时同步加右、减左，用计数 O(1) 维护，绝不每个窗口重头算。
- 20练熟「定长窗口 + 比计数」后，去同类题迁移：LC567 只把「收集所有起点」改成「存不存在」；再上一层到变长窗口 LC76，合法条件从「计数完全相等」放宽成「覆盖 t」。也可以问问 AI 助教「定长窗口和变长窗口的判定条件差在哪」。
⚠️ 容易写错的地方
✗ 错：窗口右移只加右端、忘了减左端
✓ 对：右进 win[s[i]]+=1 后，当 i 大于等于 m 时左出 win[s[i-m]]-=1
窗口长度固定为 m，只进不出会越滑越长，计数全错
✗ 错：每个窗口切片排序再和 p 比
✓ 对：维护一份计数，用 win == need 一次比对
排序每窗 O(k log k)，整体退化到 O(nk log k)；比计数才是 O(1) 一步
✗ 错：p 比 s 还长却不先判，照样开窗
✓ 对：开头 if len(p) 大于 len(s) 直接 return []
窗口根本凑不满 m 格，省掉无谓循环也避免越界
完整代码（Python / C++ / Java）
Python
class Solution:
def findAnagrams(self, s, p):
if len(p) > len(s):
return []
need = [0] * 26
win = [0] * 26
for ch in p:
need[ord(ch) - 97] += 1
ans = []
for i, ch in enumerate(s):
win[ord(ch) - 97] += 1 # 右进
if i >= len(p):
win[ord(s[i - len(p)]) - 97] -= 1 # 左出
if win == need:
ans.append(i - len(p) + 1)
return ansC++
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size(), m = p.size();
vector<int> ans;
if (m > n) return ans;
vector<int> need(26, 0), win(26, 0);
for (char ch : p) need[ch - 'a']++;
for (int i = 0; i < n; i++) {
win[s[i] - 'a']++; // 右进
if (i >= m)
win[s[i - m] - 'a']--; // 左出
if (win == need)
ans.push_back(i - m + 1);
}
return ans;
}
};Java
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int n = s.length(), m = p.length();
List<Integer> ans = new ArrayList<>();
if (m > n) return ans;
int[] need = new int[26], win = new int[26];
for (char ch : p.toCharArray()) need[ch - 'a']++;
for (int i = 0; i < n; i++) {
win[s.charAt(i) - 'a']++; // 右进
if (i >= m)
win[s.charAt(i - m) - 'a']--; // 左出
if (Arrays.equals(win, need))
ans.add(i - m + 1);
}
return ans;
}
}复杂度
时间复杂度
O(n)
每个字符进窗口、出窗口各一次；每步比一次定长 26 计数是常数
空间复杂度
O(1)
need 和 win 各是固定 26 长度数组，与输入规模无关
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找到字符串中所有字母异位词 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不每个窗口排序再比，而要维护计数？+
排序每个窗口要 O(k log k)，整体退化到 O(nk log k)；维护 win 数组每步只改两格、比一次定长 26 计数，整体 O(n)。
win == need 比的是什么，开销多大？+
比的是两个长度 26 的计数数组逐位相等，开销是常数 26，与字符串长度无关，所以不影响整体线性复杂度。
字符集不止小写字母怎么办？+
把 26 长度数组换成哈希表计数即可；但用哈希表时计数减到 0 的键要删掉，否则 {x:0} 残留会让相等判断出错——这正是定长数组的优势。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。