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

【题目】：438. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        vector<int> curVec(26, 0); // 统计p中字母出现的次数
        for(char c : p) {
            curVec[c - 'a']++;
        }
        for(int l = 0, r = 0; r < s.size(); ++r) {
            curVec[s[r] - 'a']--; // 右侧字母进入滑窗
            // 如果某个字母正好满足要求，并且此时窗口长度 = p.size()，说明此时滑窗内是p的异位词
            if(curVec[s[r] - 'a'] == 0 && r - l + 1 == p.size()) {
                res.push_back(l);
                // 缩小窗口
                curVec[s[l++] - 'a']++;
            }
            // 如果某个字母没有出现过，或 滑窗内出现次数>p中字母出现的次数，缩小滑窗
            while(curVec[s[r] - 'a'] < 0) {
                curVec[s[l++] - 'a']++;
            }
        }
        return res;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

这题要求字符串中的字母异位词，首先先用curVec存储字符串p中字母出现的次数，当滑窗扩大时，左侧字母进入滑窗，curVec[s[r] - ‘a’]–，有两种情况需要讨论：

1. 此时curVec[s[r] - ‘a’] == 0：这时候说明s[r]这个字母的出现次数 = p中s[r]字母出现的次数，如果滑窗的长度 = p的长度，说明滑窗内的字符串是p的异位词，此时可以缩小窗口，记录结果。
2. 此时 curVec[s[r] - ‘a’] < 0：这时候又分为两种情况：
   • 情况1. s[r]没有出现过
   • 情况2. s[r]在滑窗内出现的次数 > p中s[r]出现的次数
     无论是哪种情况，只要缩小窗口，直到curVec[s[r] - ‘a’] == 0即可。