題目來源
一道滑動窗口問題，我一開始想著用一個哈希表存儲p各個字母出現(xiàn)的頻次，然后滑動窗口對其進行加減操作歌亲，當(dāng)每一個字母都是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陷揪，不過寫的有點長≡忧睿可以進一步修改優(yōu)化悍缠。代碼如下：
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;
}
};
