滑动窗口法:
class Solution {
public:vector<int> findAnagrams(string s, string p) {unordered_map<char,int> need,window;for(char c : p) need[c]++;int left = 0,right = 0;int valid = 0;vector<int> res;//窗口数据更新while(right < s.size()){char c = s[right];right++;//先判断新来的在不在要求的字串中,不在的话计数不变if(need.count(c)){window[c]++;//再判断新来的字符计数是否满足条件了,满足条件数则valid++if(window[c] == need[c]){valid++;}}//子循环判断左窗口是否需要收缩,right-left就是当前窗口大小,因为right++导致窗口区间是[left,right)while(right - left >= p.size()){//当窗口符合条件时,把起始索引加入res,记录答案if(valid == need.size()){res.push_back(left);}char d = s[left];left++;//收缩后,对窗口计数更新//先判断舍弃的在不在要求的子串中,不在的话计数不变if(need.count(d)){ //再判断舍弃的字符计数是否满足条件了if(window[d] == need[d]){valid--;}window[d]--;//这里window一定要在判断后--,跟上面右移的时候反过来对称,右移是先++}}}return res;}
};