LeetCode 567中等滑动窗口 · 定长计数
字符串的排列 图解题解
s2 里藏着 s1 的某种排列吗？用一个定长取景框滑过去，计数相同就算中。
像用一个和 s1 等长的取景框在 s2 上逐格平移：框的宽度固定，每往右移一格就纳入右边新字母、丢掉左边旧字母。不关心顺序，只比框内每个字母的数量和 s1 的字母计数是否相同——一致就找到了一个排列。定长窗口，一进一出，线性扫完。
这道题到底在问什么
给两个字符串 s1、s2，判断 s2 中是否存在一个子串，是 s1 的排列。
- s1
- "ab"
- s2
- "eidbaooo"
- 输出
- true
最优解：一步一步想明白
- 3窗口长度始终等于 len(s1)，每右移一格就加右字符、删左字符。
- 4need: a=1,b=1排列不看顺序，只看计数。
- 5不匹配长度已经是 2，但字符不对。
- 6仍不匹配定长窗口每次只做一进一出。
- 7缺 a计数还没对上。
- 8命中顺序不同没关系，计数相同就是一个排列。
- 9找到排列一旦命中就可以结束。
- 10多了无关字符不是每个含 a 的窗口都匹配，还要 b 的数量也对。
- 11先扩到 len(s1)定长窗口常见边界：还没凑够长度时不要比较。
- 12扫完没命中则 false本例在 ba 处窗口频次匹配 → 返回 true。若扫完整个 s2 都没有任一长度窗口的频次等于 s1，则返回 false。
- 15看到“是否包含某个排列/异位词”，就想到固定长度滑动窗口。
⚠️ 容易写错的地方
✗ 错：窗口长度没固定就比较
✓ 对：先保证窗口长度等于 len(s1)
长度不同的窗口不可能是排列
✗ 错：只判断字符是否出现
✓ 对：必须比较出现次数
s1="aab" 时一个 a 不够
完整代码（Python / C++ / Java）
Python
class Solution:
def checkInclusion(self, s1, s2):
if len(s1) > len(s2): return False
need = [0]*26; win = [0]*26
for ch in s1: need[ord(ch)-97] += 1
for i, ch in enumerate(s2):
win[ord(ch)-97] += 1
if i >= len(s1): # 滑出最左
win[ord(s2[i-len(s1)])-97] -= 1
if win == need: return True # 频次相等=排列
return FalseC++
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) return false;
vector<int> need(26), win(26);
for (char ch : s1) need[ch-'a']++;
for (int i = 0; i < s2.size(); i++) {
win[s2[i]-'a']++;
if (i >= (int)s1.size()) win[s2[i-s1.size()]-'a']--; // 滑出最左
if (win == need) return true; // 频次相等=排列
}
return false;
}
};Java
class Solution {
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 ch : s1.toCharArray()) need[ch-'a']++;
for (int i = 0; i < s2.length(); i++) {
win[s2.charAt(i)-'a']++;
if (i >= s1.length()) win[s2.charAt(i-s1.length())-'a']--; // 滑出最左
if (Arrays.equals(win, need)) return true; // 频次相等=排列
}
return false;
}
}套路模板 · 定长计数窗口
class Solution:
def fixedWindow(self, s, k):
win = [0] * 26
for i, ch in enumerate(s):
win[ord(ch) - 97] += 1
if i >= k:
win[ord(s[i - k]) - 97] -= 1
if i >= k - 1 and ok(win):
return True
return False复杂度
时间复杂度
O(n)
窗口滑过 s2 一遍，每步比较 O(26)=O(1)
空间复杂度
O(1)
两个 26 大小的频次数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字符串的排列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
定长滑动窗口(长度=len(s1))，维护窗口内 26 字母频次；每滑一格「加右删左」，频次数组与 s1 的相等就说明窗口是 s1 的一个排列。
每步比较 26 个数会慢吗？+
O(26)=O(1) 常数；也可维护一个 matched(已匹配字母数)，加减时增量更新，matched 到 26 即命中，把比较降到真 O(1)。
复杂度多少？+
窗口滑过 s2 一遍 O(n)，每步比较 O(26)=O(1) → 总 O(n)；两个 26 大小数组 O(1) 空间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。