一：题目
解释：比如abc的异位词就是 bac cab cba这种重排列子串，我们返回所有异位词的起始索引即可
二：算法
首要的问题是我们在s中取出和p等长的字符串后，此时如何判断两个字符串是异位词？
这种判断某个变量的个数，采取哈希表是最高效的，p在一个哈希表内，我们在s中取出的字符串也在一个哈希表内，对比两个哈希表是否相等即可！
而s和p又都仅仅包含小写字母，所以只有26种可能，所以用一个26大小的数组来模拟哈希表，这样a对应0下标，z对应25下标，刚刚好！所以得到任意一个小写字母，只需减去'a'即可变成0~25范围内的下标！
①：暴力
left从左到右以不同元素作为起点，然后right向右遍历，取到和p等长的字符串，该字符串和p字符串都放在哈希表中比较即可，比较完成，哈希表双双情况，然后下一次left++，right再次从left开始位置向后取和p等长字符串再放进哈希表和p所以的哈希表比较，以此类推....
所以时间复杂度为O(N^2)
②：滑动窗口普通版
例子数组：s = "cbaebabacd", p = "abc"
暴力能优化的点：
1：我们不用将哈希表全部清空，比如现在哈希表中是s中的"cba"，下次我们只需清除'c'，然后填入'e'，形成"bae"即可！
2：所以right也不用在回到前面再次向后遍历取和p一样长的字符串了，其只需无脑++
所以其实这个题目是最适合采取滑动窗口的题目，双指针甚至移动的频率和步长都一致！
但是这个滑动窗口+判断两个哈希表是否相等(check函数)的算法，并不优秀，因为所用调用check函数的时间复杂度为 O(n)！因为单次调用check函数是O(26)，而最坏情况是调用s字符串的个数n次，所以为O(26n)，大O后为O(n)！所以每次都调用check函数是很影响速率的！
③：滑动窗口优秀版
而更优秀版本是更难理解的，其时间复杂度低至O(1)，因为其不直接去判断两个哈希表是否相等，而是用一个变量count来表示窗口内的字符串的有效字符的个数，而有效字符指的就是p字符串中的字符，但是这里有个很难理解的的：
例子1：
p字符串："abc"
窗口字符串："bbb"
此时有效字符为'a','b','c'，但是我们的count不是为3，而是为1！
所以有效字符指的是：
由于p中的a只有一个，所以窗口中的a只会有一个有效
由于p中的b只有一个，所以窗口中的b只会有一个有效
由于p中的c只有一个，所以窗口中的c只会有一个有效
而此时窗口中全部b，但是只有一个b有效，所以count为1！
所以当count==3的时候，此时表示窗口中一定是1个a，1个b，1个c
例子2：
p字符串："abb"
窗口字符串："cbb"
此时有效字符为'a','b'，但是我们的count不是为1，而是为2！
所以有效字符指的是：
由于p中的c只有一个，所以窗口中的c只会有一个有效
由于p中的b有两个，所以窗口中的b有两个算作有效
而此时窗口中有两个b，所以count为2！
所以当count==3的时候，此时表示窗口中一定是1个a，2个b
总结：
count统计当前窗口中满足「字符频率 ≤ 目标频率」的字符种类数
所以count的理解至关重要，岂不是遇见和p字符串中字符相同的就++，而是有个数限制！
换算为代码思路：
1：进窗口：先判断字符 c 在存储窗口的哈希表中的频率若还未达到存储p哈希表频率，则count++
2：出窗口：若出窗口后，字符 c 在存储窗口的哈希表中的频率<存储p哈希表频率，则count--
三：代码
①：普通版
普通版就是更易理解的版本，其虽然不如优秀版，但是由于其仍采取了滑动窗口的思路，所以仍以通过代码测试：
class Solution {
public:
// 检测两个哈希表是否相等
bool check(int* hash1, int* hash2) {
//逐元素检测
for (int i = 0; i <= 25; i++) {
if (hash1[i] != hash2[i])
return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
//两个哟挂数组模拟的哈希表
int hash1[26] = {0};
int hash2[26] = {0};
vector<int> ret;//存储返回值的数组
int n = s.size();//限制right++的上限
int m = p.size();//p字符串的长度
for (auto c : p) {//将p字符串存储进hash2
hash2[c - 'a']++;
}
for (int left = 0, right = 0, count = 0; right < n; right++) {
//进窗口
int in = s[right] - 'a';//将s中的字符转换为0~25下标
hash1[in]++;//将字符存储进hash1 让v值++
//窗口过长
while (right - left + 1 > m) {
//出窗口
int out = s[left++] - 'a';//将s中的字符转换为0~25下标
hash1[out]--;//从hash1中移除字符 让v值--
}
//窗口符合要求的时候，去判断记录结果
bool ret2 = check(hash1, hash2);
if (ret2 == true)
ret.push_back(left);
}
return ret;
}
};
②：优秀版
写法1：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash1[26]={0};
int hash2[26]={0};
vector<int> ret;
int n =s.size();
int m = p.size();
for(auto c:p)
{
hash2[c-'a']++;
}
for(int left=0,right=0,count =0;right<n;right++)
{
int in = s[right]-'a';
if(hash1[in]<hash2[in]) count++;//进窗口前 如果字符频率 < 目标频率 则count++
hash1[in]++;
while(right-left+1>m)
{
int out = s[left++]-'a';
hash1[out]--;
if(hash1[out] <hash2[out]) count--;//出窗口后 如果字符频率 < 目标频率 则count++
}
//有效字符个数count 等于p字符串的长度 则代表是异位词！
if(count==m) ret.push_back(left);
}
return ret;
}
};
写法2：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash1[26]={0};
int hash2[26]={0};
vector<int> ret;
int n =s.size();
int m = p.size();
for(auto c:p)
{
hash2[c-'a']++;
}
for(int left=0,right=0,count =0;right<n;right++)
{
int in = s[right]-'a';
hash1[in]++;
if(hash1[in]<=hash2[in]) count++;//进窗口后 如果字符频率 <= 目标频率 则count++
while(right-left+1>m)
{
int out = s[left++]-'a';
hash1[out]--;
if(hash1[out] <hash2[out]) count--;//出窗口后 如果字符频率 < 目标频率 则count++
}
//有效字符个数count 等于p字符串的长度 则代表是异位词！
if(count==m) ret.push_back(left);
}
return ret;
}
};
总结二者：
1：两种写法的区别在于，前者是在进窗口之前先判断一下字符频率 < 目标频率？所以如果小于，则代表你这次进窗口是会让count++的！而后者是进窗口之后，再判断字符频率 <= 目标频率?因为你进了之后，才让二者频率相等，则你的count仍然是会++的！
2：我们用数组来模拟哈希表的本质就是，让26个字符对应0~25下标，所以一定要记得-'a'！
3：不用担心字符在进窗口后，此字符在hash2中不存在，因为不存在，则不会通过if语句，不会影响到count
4：不用担心出窗口的字符在hash2中不存在，因为不存在，也不会通过if语句，不会影响到count