2021-10-24

• C++

class Solution {
public:
    vector findAnagrams(string s, string p) {
        vector p_cnt(26, 0), s_cnt(26, 0);

        for(auto cc: p){
            p_cnt[cc - 'a'] ++;
        }
        int cur_cnt;
        vector ans;
        int ii, jj;
        int last_idx, cur_idx;
        
        int k = p.size();
        cur_cnt = 0;

        for(ii = 0, jj = 0; ii < s.size(); ++ ii){
            if(ii >= k){
                last_idx = s[jj] - 'a';
                if(p_cnt[last_idx]){
                    
                    s_cnt[last_idx] --;
                    if(s_cnt[last_idx] < p_cnt[last_idx]){
                        -- cur_cnt;
                    }
                }
                ++ jj; 
            }
            cur_idx = s[ii] - 'a';
            if(p_cnt[cur_idx]){
                s_cnt[cur_idx] ++;
                if(s_cnt[cur_idx] <= p_cnt[cur_idx]){
                    cur_cnt ++;
                }
                
            }
            if(cur_cnt == k){
                ans.push_back(ii - k + 1);
            }
        }
        return ans;
    }
};

n为字符串S长度， k为字符串P长度。

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。