固定长度滑动窗口维护 26 维字母计数，窗口进出各一次，O(n)。
OJ: leetcodecn
题目 ID: find-all-anagrams-in-a-string
难度:普及+/提高
标签:哈希表字符串滑动窗口cpppython
日期: 2026-07-28 22:05
题意
给定字符串 s 和 p，找出 s 中所有 p 的字母异位词子串的起始下标。
思路
暴力排序每个窗口 O(nk log k)。优化：用 26 维计数器维护窗口内字符频次，每次窗口滑动时只更新进出两个字符，然后比较整个计数数组是否归零。
代码
cpp
/**
* Author by Rainboy
*/
// main.cpp：滑动窗口维护 26 维计数，O(n)。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size(), m = p.size();
if (n < m)
return {};
array<int, 26> cnt = {};
for (char ch : p)
cnt[ch - 'a']++;
vector<int> ans;
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']--;
if (i >= m)
cnt[s[i - m] - 'a']++;
if (i >= m - 1) {
bool ok = true;
for (int x : cnt)
if (x) {
ok = false;
break;
}
if (ok)
ans.push_back(i - m + 1);
}
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s, p;
cin >> s >> p;
auto v = Solution().findAnagrams(s, p);
for (int x : v)
cout << x << ' ';
return 0;
}python
#!/usr/bin/env python3
from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
n, m = len(s), len(p)
if n < m:
return []
cnt = [0] * 26
for ch in p:
cnt[ord(ch) - 97] += 1
ans = []
for i in range(n):
cnt[ord(s[i]) - 97] -= 1
if i >= m:
cnt[ord(s[i - m]) - 97] += 1
if i >= m - 1:
if all(x == 0 for x in cnt):
ans.append(i - m + 1)
return ans
def main() -> None:
s = input().strip()
p = input().strip()
ans = Solution().findAnagrams(s, p)
print(*ans)
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(n)，每个字符进出各一次，每次检查 26 个计数（常数）。
- 空间复杂度：O(1)，固定 26 长度的计数数组。
总结
固定长度滑动窗口配合计数数组做"异位词匹配"，是字符串模式匹配的经典模型。窗口滑动时只维护变化的两端，将每次匹配的时间从 O(k log k) 降到 O(1)。