题目来源
一道滑动窗口问题，我一开始想着用一个哈希表存储p各个字母出现的频次，然后滑动窗口对其进行加减操作，当每一个字母都是0的时候，是我们想要的。
代码如下：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> maps(26, 0);
vector<int> com(maps);
vector<int> res;
int n1 = s.size(), n2 = p.size();
for (int i=0; i<n2; i++)
maps[p[i] - 'a']++;
for (int i=0; i<n2; i++) {
maps[s[i] - 'a']--;
}
if (com == maps)
res.push_back(0);
for (int i=n2; i<n1; i++) {
maps[s[i-n2] - 'a']++;
maps[s[i] - 'a']--;
if (com == maps)
res.push_back(i-n2+1);
}
return res;
}
};
可以AC，不过写的有点长。可以进一步修改优化。代码如下：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> maps(26, 0);
vector<int> res;
int n1 = s.size(), n2 = p.size();
for (int i=0; i<n2; i++)
maps[p[i] - 'a']++;
int left = 0, right = 0, cnt = n2;
while (right < n1) {
if (maps[s[right++] - 'a']-- >= 1)
cnt--;
if (cnt == 0)
res.push_back(left);
if (right - left == n2 && maps[s[left++] - 'a']++ >= 0)
cnt++;
}
return res;
}
};
