字符串的排列 图解题解
s2 里藏着 s1 的某种排列吗？用一个定长取景框滑过去，计数相同就算中。
像用一个和 s1 等长的取景框在 s2 上逐格平移：框的宽度固定，每往右移一格就纳入右边新字母、丢掉左边旧字母。不关心顺序，只比框内每个字母的数量和 s1 的字母计数是否相同——一致就找到了一个排列。定长窗口，一进一出，线性扫完。
这道题到底在问什么
- 输入
- s1 = "ab"，s2 = "cbaebd"
- 输出
- true（s2 的 "ba" 正好是 "ab" 的排列）
最优解：一步一步想明白
- 3核心就一句：窗口长度钉死等于 s1，滑动时「进的加一、出的减一」，每步比一下窗口里的字母个数和需求是否完全相同。
- 4先搭起始窗口：把下标 0 到 0 的字母圈进来，目前窗口里有 {c:1}。继续往右凑够 2 个字母。
- 5先搭起始窗口：把下标 0 到 1 的字母圈进来，目前窗口里有 {c:1，d:1}。窗口长度凑到 2 了，正好等于 s1 的长度。
- 6起始窗口里是 {c:1，d:1}，和需求 {a:1，b:1} 不一样，不是排列。窗口开始向右滑。
- 7窗口准备向右滑一格。标红的下标 0（字母 c）马上要滑出窗口，绿色的下标 2（字母 e）马上要进窗口。
- 8窗口滑到下标 1~2，里面是 {d:1，e:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 9窗口准备向右滑一格。标红的下标 1（字母 d）马上要滑出窗口，绿色的下标 3（字母 c）马上要进窗口。
- 10窗口滑到下标 2~3，里面是 {e:1，c:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 11窗口准备向右滑一格。标红的下标 2（字母 e）马上要滑出窗口，绿色的下标 4（字母 d）马上要进窗口。
- 12窗口滑到下标 3~4，里面是 {c:1，d:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 13窗口准备向右滑一格。标红的下标 3（字母 c）马上要滑出窗口，绿色的下标 5（字母 c）马上要进窗口。
- 14窗口滑到下标 4~5，里面是 {d:1，c:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 15窗口准备向右滑一格。标红的下标 4（字母 d）马上要滑出窗口，绿色的下标 6（字母 e）马上要进窗口。
- 16窗口滑到下标 5~6，里面是 {c:1，e:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 17窗口准备向右滑一格。标红的下标 5（字母 c）马上要滑出窗口，绿色的下标 7（字母 d）马上要进窗口。
- 18窗口滑到下标 6~7，里面是 {e:1，d:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 19窗口准备向右滑一格。标红的下标 6（字母 e）马上要滑出窗口，绿色的下标 8（字母 b）马上要进窗口。
- 20窗口滑到下标 7~8，里面是 {d:1，b:1}，和需求 {a:1，b:1} 不一样，继续往右滑。
- 21窗口准备向右滑一格。标红的下标 7（字母 d）马上要滑出窗口，绿色的下标 9（字母 a）马上要进窗口。
- 22窗口滑到下标 8~9，里面是 {b:1，a:1}，正好等于需求 {a:1，b:1}。命中排列，返回 true。
- 23滑动过程里，高亮这一段连续子串的字母个数和 s1 完全一致，它就是 s1 的一个排列，最终答案 true。
⚠️ 容易写错的地方
✗ 错：用排序后比较，每个窗口都排一次序
✓ 对：用计数数组，进 +1 出 -1 增量维护
每个窗口排序是 O(k log k)，n 个窗口更慢；计数数组每步只花 O(1)
✗ 错：窗口右移后忘了把滑出的字母个数减一
✓ 对：下标超过 k 时立刻把 s2[i-k] 的计数 -1
不减一窗口会越变越长，计数永远对不上需求，得不到正确结果
✗ 错：只看字母种类对上就判为排列
✓ 对：要求每个字母的个数都完全相等
排列要求个数也一样，比如需 2 个 a 只来 1 个 a 不算
完整代码（Python / C++ / Java）
Python
def checkInclusion(s1, s2):
if len(s1) > len(s2): return False
need = [0]*26 # s1 各字母需求
win = [0]*26 # 当前窗口各字母
for c in s1: need[ord(c)-97] += 1
k = len(s1)
for i, c in enumerate(s2):
win[ord(c)-97] += 1 # 进的 +1
if i >= k: # 超长了，左边滑出
win[ord(s2[i-k])-97] -= 1 # 出的 -1
if win == need: return True # 个数全相同
return FalseC++
bool checkInclusion(string s1, string s2){
if (s1.size() > s2.size()) return false;
int need[26]={0}, win[26]={0};
for (char c : s1) need[c-'a']++;
int k = s1.size();
for (int i = 0; i < (int)s2.size(); i++){
win[s2[i]-'a']++;
if (i >= k) win[s2[i-k]-'a']--;
if (memcmp(need,win,sizeof need)==0) return true;
}
return false;
}Java
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] need = new int[26], win = new int[26];
for (char c : s1.toCharArray()) need[c-'a']++;
int k = s1.length();
for (int i = 0; i < s2.length(); i++) {
win[s2.charAt(i)-'a']++;
if (i >= k) win[s2.charAt(i-k)-'a']--;
if (Arrays.equals(need, win)) return true;
}
return false;
}复杂度
时间
O(n)
窗口在 s2 上滑一趟，每步只做一加一减加一次 26 长度的定长比较
空间
O(1)
只用两个长度 26 的计数数组，和字符串长短无关
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字符串的排列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么窗口长度可以固定？+
排列和 s1 长度一样，所以子串长度必然等于 len(s1)。窗口长度钉死成 len(s1)，只需平移、不用伸缩。
怎么快速判断两个窗口的字母个数相同？+
用两个长度 26 的计数数组，分别记需求和当前窗口。每步比较两个数组是否相等即可，比较代价是常数。
能不能不用 26 长度数组，每次都数一遍窗口？+
可以但更慢。每步重新数窗口是 O(k)，整体 O(n·k)；用计数数组增量更新让每步降到 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 字符串的排列 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。