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> 统计频率。但是哈希表内存开销大（空间换时间）。
2. 滑动窗口遍历 s：维护一个长度为 p.size() 的窗口，统计窗口内字母的频率，与 p 的频率对比。 若窗口内字母频率与 p 完全一致，则记录窗口的起始索引。 窗口滑动时，移除左边界字母的计数，添加右边界字母的计数，维护窗口长度不能超过 p.size()。这是写窗口收缩条件代码。

注意要点

1. 边界检查：if(len_s<len_p) 如果字符串 s 长度小于 p，直接返回空结果。注意不要写 return ;，函数的返回类型是 vector<int>，return 语句必须返回一个 vector 对象。
2. 滑动窗口逻辑：循环内先写窗口扩张代码，再写窗口收缩条件判断代码，再写窗口铺满后（窗口长度大于等于字符串 p 长度）的条件判断代码。只有当窗口完全形成（长度等于 len_p）时才有比较两个 vector 数组字母频率是否相同的必要。
3. 索引判断：if(right>=len_p-1) 这个判断条件是因为 right 是从索引 0 的位置开始走的，所以要 -1。例如当 right 为 len_p-1 时，窗口大小为 len_p，刚好满足比较条件。
4. 学习建议：做题前先理解题目和知识点，尝试编写大体代码。遇到难点可查阅资料或借助工具辅助理解，然后独立复现代码并验证逻辑，避免直接照搬片段代码，以构建完整的算法逻辑体系。