438. 找到字符串中所有字母异位词
3 min
题目
解法：滑动窗口
思路
核心思想是使用滑动窗口配合字符计数数组。通过维护与p等长的窗口，动态调整左右指针确保窗口内字符频率与p一致。
正确性在于：当窗口长度等于p长度且字符计数完全匹配时即为异位词。移动右指针扩展窗口时增加字符计数，若某字符超量则移动左指针收缩窗口直至恢复有效状态，该过程保证不会遗漏任何有效窗口。
- Step 1: 初始化p的字符计数数组num
- Step 2: 用now数组记录当前窗口字符计数，left指针起始为0
- Step 3: 遍历s扩展右指针，更新now计数
- Step 4: 若当前字符超量则收缩左指针直至恢复有效
- Step 5: 窗口长度等于p时记录左指针位置
复杂度
- 时间复杂度: ，n为s长度，每个字符最多被左右指针各访问一次
- 空间复杂度: ，固定使用两个长度26的计数数组
代码
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> num(26, 0);
for (auto c : p) {
num[c - 'a']++;
}
vector<int> ans;
vector<int> now(26, 0);
int left = 0;
for (int right = 0; right < s.size(); right++) {
int r_idx = s[right] - 'a';
now[r_idx]++;
while (now[r_idx] > num[r_idx]) {
int l_idx = s[left] - 'a';
now[l_idx]--;
left++;
}
if (right - left + 1 == p.size()) {
ans.push_back(left);
}
}
return ans;
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> num(26, 0);
for (auto c : p) {
num[c - 'a']++;
}
vector<int> ans;
vector<int> now(26, 0);
int left = 0;
for (int right = 0; right < s.size(); right++) {
int r_idx = s[right] - 'a';
now[r_idx]++;
while (now[r_idx] > num[r_idx]) {
int l_idx = s[left] - 'a';
now[l_idx]--;
left++;
}
if (right - left + 1 == p.size()) {
ans.push_back(left);
}
}
return ans;
}
};