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

题目

链接：leetcode链接

思路分析（滑动窗口）

很容易想到，这个题目要求我们在字符串s中找到一个定长的窗口让窗口里面出现异位词。

OK，先思考一下怎么快速判断两个字符串是否是异位词？
比较简单的方法是，把字符串的每一个字符往哈希表里面丢，然后比较哈希表即可。
异位词只关心字母的个数，不关心顺序，所以使用哈希表可以比较快速的判断。
记p为hash1，s为hash2

然后，我们只需要去维护一个定长的窗口，去与p去比较即可。

OK，
那么先left，right = 0;
然后进窗口，hash2[right]++
当窗口的长度大于p的长度时，开始出窗口，
hash2[left]–，left++；

当hash1 == hash2 时，就left即满足要求。

优化

注意，这里hash表里面仅仅存的是字符，总共26个小写字母，直接遍历一遍出结果就可以，还是很好比较的，但是，如果存的不是字符呢？存的是字符串怎么办？
这是再遍历hash去比较，比较的麻烦。
这里提出一种可以优化的方案。

大体思路不变，主要是优化hash表的比较。

我们增加一个变量count，来记录窗口中的有效元素的个数。
我们在进窗口后和出窗口前都去维护这个count变量即可。

那么什么是有效元素呢？
我们来举一个例子，就以示例1为例
s = “ccaebabacd” ， p = “abc”
开始 hash2[s[right]] 进入hash表后，1 <= hash1[c]，那么这就是有效元素，count++
right++；
hash2[s[right]]进入hash表后，2 > hash1[c] ，这就是无效元素，count就不变

接着a入窗口，有效元素，count++，
接着e如窗口，无效元素，count不变

这时发现窗口长度超过了p的长度，就需要出窗口，
出窗口前，发现hash2[left] == 2 > hash1[left]，那么说明出的这个元素是无效元素，count不需要改变
下一次出窗口时，发现hash2[c] <= hash1[c]，诶，就是有效元素了，count–

当count == 3时，left就是符合要求的下标。

代码

优化前代码

 vector<int> findAnagrams(string s, string p) {int hash1[26] = {0},hash2[26] = {0};int len = p.size();vector<int> v;for(auto e:p) {hash1[e-'a']++;}for(int left = 0,right = 0;right < s.size();++right){char in = s[right];hash2[in - 'a']++;if(right - left + 1 > len){char out = s[left];hash2[out - 'a']--;left++;}int i = 0;for( i = 0;i<26;i++){if(hash1[i]!=hash2[i])break;}if( i == 26)v.push_back(left);}return v;}

优化后代码

vector<int> findAnagrams(string s, string p) {int hash1[26] = {0},hash2[26] = {0};int len = p.size();int count = 0;vector<int> v;for(auto e:p) {hash1[e-'a']++;}for(int left = 0,right = 0;right < s.size();++right){char in = s[right];hash2[in - 'a']++;if(hash2[in - 'a'] <= hash1[in - 'a']){count++;}if(right - left + 1 > len){char out = s[left];if(hash2[out - 'a'] <= hash1[out - 'a']) count--;hash2[out - 'a']--;left++;}if(count == len)v.push_back(left);}return v;}