力扣hot9---滑动窗口

题目：

先记录一下（没想到有生之年，还能）：其实还能优化，后面会讲述优化思路

 思路：

滑动窗口的大小就是固定的，就是len_p。那么依次将窗口从s的最左端向右滑动。在当下的窗口中，判断窗口中s的子串和p串中元素种类及个数是否匹配即可（这里用cnt_s，cnt_p分别记录对应元素的个数）。

代码：

C++：

class Solution {
public:
    int cnt_s[26]={0};
    int cnt_p[26]={0};
    bool check(){
        for(int i=0;i<26;i++){
            if(cnt_s[i]!=cnt_p[i]){
                return false;
            }
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int len_s=s.size();
        int len_p=p.size();
        //记录cnt_p
        for(int i=0;i<len_p;i++){
            cnt_p[p[i]-'a']++;
        }
        for(int i=0;i<=len_s-len_p;i++){
            if(i==0){
                for(int j=0;j<len_p;j++){
                    cnt_s[s[j]-'a']++;
                }
            }
            else{
                cnt_s[s[i-1]-'a']--;
                cnt_s[s[i+len_p-1]-'a']++;
            }
            if(check()){
                res.push_back(i);
            }
        }
        return res;
    }
};

python：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt_s=[0]*26
        cnt_p=[0]*26
        res=[]
        len_s,len_p=len(s),len(p)
        for i in p:
            cnt_p[ord(i)-ord('a')]+=1
        for i in range(0,len_s-len_p+1):
            if i==0:
                for j in s[0:len_p]:
                    cnt_s[ord(j)-ord('a')]+=1
            else:
                cnt_s[ord(s[i-1])-ord('a')]-=1
                cnt_s[ord(s[i+len_p-1])-ord('a')]+=1
            if cnt_s==cnt_p:
                res.append(i)
        return res
        

注意python中的写法：

cnt_s=[0]*26
cnt_p=[0]*26

对标于C++的cnt_p [ p [ i ] - 'a' ]++ ; 

cnt_p[ord(i)-ord('a')]+=1

cnt_s==cnt_p

优化

可以在窗口滑动后，先判断新加入的元素是否属于p串（这里维护一个哈希表），如果不属于，那么左窗口直接跳到新加入元素的下一个位置。