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

欢迎跳转我的主页：羑悻的小杀马特-CSDN博客

目录：

一·题目简述：

二·思路汇总：

三·解答代码：

---

一·题目简述：

leetcode题目链接：. - 力扣（LeetCode）

二·思路汇总：

哈希+滑动窗口：即窗口里就是固定的len（p）;然后比较两个hash表内数据是否完全对着上，如果是那么就保存left，依次循环进行下去。

这里画图说明一下步骤：

这里可以优化一下：

比如在建立hash的时候由于这里都是小写字母；故可以建立可放26个字母的hash（利用映射）  

还有就是这里字母数量少，以及找的只是单个字母，如果要是单个字符串那么，这样再去遍历比较肯定特别麻烦，因此可以考虑在入出窗口的时候就保存count来记录这个窗口内本来有模版hash表内数据的有效字符的个数，画图解释一下：

 

这时此题的要点就差不多了。

三·解答代码：

class Solution {
public:vector<int> findAnagrams(string s, string p) {int n=s.size();vector<int> v;int hash_p[26]={0};//把p内数据映射入哈希表int hash_s[26]={0};//入到窗口的数据for(auto e:p){hash_p[e-'a']++;}int len=p.size();for(int left=0,right=0,count=0;right<n;right++){int in=s[right]-'a';//入窗口数据int out =s[left]-'a';//出窗口数据//入窗口：：hash_s[in]++;//这里如果后面直接遍历两个hash表比较，复杂度比较高，故选择开始入数据和出数据都完成记录。if(hash_s[in]<=hash_p[in]){count++;//记录有效字母的个数}//出窗口：if(right-left+1>len){if(hash_s[out]<=hash_p[out]){count--;}hash_s[out]--;left++;1}//出窗口后更新结果：if(count==len){v.emplace_back(left);}}return v;}
};