Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".Example 2:
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".做这道题目的时候正在生病中，想想每天刷一道leetcode的习惯不能破，还是坚持做下来了，为自己点个赞。当然做的是一塌糊涂，做了一个小时多，用了一个很扯淡的方法AC了，先来说说我的做法。
这个题目明显是Hash表应用，但我的想法局限在只是用一个hash表里面了（建立string p的Hash表，在划窗遍历s时减去Hash表中相应项的数值，若在一个窗口中Hashp数组为全0，则是Anagrams，若某个字母进入窗口后使得Hashp中对应的项小于0，则窗口需要向后滑动），这样在划窗遍历string s的时候非常麻烦，需要定义了head和tail两个指针表示窗的起始和终止坐标，flag表示的是当窗口新进入一个字母使得Hash表中某一项小于0（即已经不可能是Anagrams时）的情况。具体的head的前进规则：如果flag为0，且当前窗口满足条件，则前进一格，否则一直前进到Hashp[++head] == 0为止；如果当前的flag为1，则head前进到s[head] == s[tail - 1]的位置。
这么说太模糊不清了，以Example1为例具体说明一下：
s: "cbaebabacd" p: "abc"0. Hashp的值为[1,1,1,0......,0],开始时head和tail均在起始位置为0。
1. 当第一次窗口填满时，Hashp的值为全0，此时head = 0, tail= 2，记录下起始点head值。
2. 窗口向后移动一格，head = 1，tail走到3，发现值为e使得Hashp[4](即e-'a')为-1，此时说明这个窗口不满足条件，head前进至第一个等于e的位置且要越过它，这里前进到head = 4，此时tail = 4.
3. tail继续往后走至tail=6,窗口中为"bab",不满足条件，同2，head越过第一个和tail-1所在位置相同的值即b，到达head = 5.
4. head = 5后tail走到7，窗口中为"aba"，不满足条件，同2，head越过a达到b，head = 6。
5. head = 6后tail走到8，窗口中为"bac",满足条件，记录此时起始点head的值,然后窗口往后移一格，head = 7。
6. 新入的值d使得Hashp[3]为-1，head一直走到head = 9才使得Hashp[3]非负，此时head值超过了s.size() - p.size()，循环结束。
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> res; if (s.size() < p.size()) return res; vector<int> Hashp(26, 0); for (int i = 0; i < p.size(); i++) Hashp[p[i] - 'a']++; int head = 0; int tail = 0; int ComeinNum = p.size() - head; int flag = 0; while (head <= s.size() - p.size()) { if (tail < head) tail = head; while (tail < s.size() && tail < head + p.size()) { Hashp[s[tail] - 'a']--; if (Hashp[s[tail] - 'a'] < 0) { tail++; flag = 1; break; } tail++; } if (flag == 1) { while (s[head] != s[tail - 1]) { Hashp[s[head] - 'a']++; head++; } Hashp[s[head] - 'a']++; head++; } else { int sum = 0; for (int i = 0; i < 26; i++) sum += Hashp[i]; if (sum == 0) { res.push_back(head); Hashp[s[head] - 'a']++; head++; } else { while (Hashp[++head] < 0) Hashp[s[head - 1] - 'a']++; } } flag = 0; } return res; } };后来一看别人做的方法，无语了，为何自己这么傻(⊙_⊙)?
既然我维护Hashp数组这么麻烦，那干脆不用维护了，直接再开一个数组Hashs表示滑动窗口里的情况就好了啊。
窗口每次都是一进一出，更新完Hashs后与Hashp对比，注意这里index的值表示的是窗口的结尾值。
class Solution {public: vector<int> findAnagrams(string s, string p) { vector<int> res; if(s.size() < p.size()) return res; vector<int> Hashs(26,0); vector<int> Hashp(26,0); for(int index = 0;index < p.size();index++) { Hashs[s[index]-'a']++; Hashp[p[index]-'a']++; } if(Hashs == Hashp) res.push_back(0); for(int index = p.size();index < s.size();index++) { Hashs[s[index] -'a']++; Hashs[s[index - p.size()] - 'a']--; if(Hashs == Hashp) res.push_back(index - p.size() + 1); } return res; }};
