LeetCode 38. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        vector<int> pf(26,0);
        vector<int> sf(26,0);
        int len_p=p.size();
        int len_s=s.size();
        for(char c:p){
            pf[c-'a']++;
        }
        if(len_s<len_p) return result; // 先处理边界问题，边界问题放到循环外部。
        // 遍历整个 s
        for(int right=0;right<len_s;right++){
            // 先写窗口扩张代码
            sf[s[right]-'a']++;
            // 再写窗口收缩条件代码
            if(right>=len_p){
                sf[s[right-len_p]-'a']--;
            }
            if(right>=len_p-1){
                if(sf==pf){
                    result.push_back(right-len_p+1);
                }
            }
        }
        return result;
    }
};

思路

1. 统计 p 的字母频率：用长度为 26 的数组（或哈希表）记录 p 中每个字母的出现次数。 本题用 vector 数组就可以，因为题目说了都是小写字母，哈希表的通用性更强，若字符串包含大小写或非字母字符，数组映射会失效，此时可用 unordered_map<char, int> 统计频率。但是哈希表内存开销大（空间换时间）。