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

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int sLen = s.size(), pLen = p.size(), validChar;// 母串长度比子串长度还小 直接返回空vectorif (sLen < pLen)return ret;// p字符串有哪些字符 分别出现了多少次// phash中值不为0的下标代表有哪些字符 phash[i]值就是该字符出现的次数int pHash[26] = {0};for (auto ch : p)pHash[ch - 'a']++;// 记录窗口中有哪些字符以及对应出现的次数int winHash[26] = {0};// 要理解这种写法 要理解两个关键字// 1. winHash  : 窗口中有哪些字符以及对应出现的次数// 2. validChar: 窗口中有效字符的个数for (int left = 0, right = 0, validChar = 0; right < s.size();right++) {// in：即将进入窗口的字符char in = s[right];// 遍历到in了 in默认进窗口 用【in在窗口中的次数++】来表征in进窗口了// 如果此时窗口中in的次数大于p中in的次数// 那么in是作为一个无效字符进的窗口 有效字符个数不变// 如果此时窗口中in的次数不大于p中in的次数// 表明in此时在窗口中是一个有效字符 有效字符个数++++winHash[in - 'a'];if (winHash[in - 'a'] <= pHash[in - 'a'])validChar++;else {char out = s[left++];if (winHash[out - 'a']-- <= pHash[out - 'a'])validChar--;}// 窗口的长度已经大于子串了if (right - left + 1 > pLen) {char out = s[left++];// out在窗口中出现的次数 <= out在p中出现的次数 有效字符个数--// 反向理解// 如果out在窗口中出现的次数 > out在p中出现的次数// out移出后 有效字符个数不变 out出去正是我们想要的// 窗口中少了一个不该出现的字符// 这使得区间中的字符越来越接近我们想要的字符组合了 即 异位词if (winHash[out - 'a']-- <= pHash[out - 'a'])validChar--;}// 前面两个if保证winLen <= pLen// 如果此时validChar == pLen即窗口中的有效字符个数等于p的长度 // ==》 winLen <= pLen && validChar == pLen ==》窗口中的字符全为有效字符// 表示我们找了“异位词” 如果此时validChar != pLen 表示:// 虽然窗口的长度<=pLen 但是窗口中的字符并不是全部有效// 还要继续添加新元素 来满足：窗口的长度为pLen且均为有效字符if (validChar == pLen)ret.push_back(left);}return ret;}
};