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

思路：字母异位词在排序后会得到相同的字符串！！！！！！

class Solution {
public:vector<int> findAnagrams(string s, string p) {int n=p.length();//p的长度vector<int> ans={};if(n>s.length()) return ans;sort(p.begin(),p.end());for(int i=0;i<=s.length()-n;i++){string a="";for(int j=i;j<i+n;j++){a+=s[j];}sort(a.begin(),a.end());if(a==p) ans.push_back(i);}return ans;}
};

以上是看了之前的字母异位词自己写出来的，超时！

因为每次检查子字符串是否是 p 的字母异位词（anagram）时，你都要对子字符串进行排序。排序操作的时间复杂度是O（nlogn） 总体是总的时间复杂度为 O((s.length() - p.length() + 1) * n log n)。

优化：滑动窗口：

可以优化的地方是使用滑动窗口技术和字符频率计数来代替排序操作。

因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

至此，一种新的判断字母异位词的方法出现了！ ！！！！！！

#include <vector>
#include <string>class Solution {
public:// 这个函数用于在字符串 s 中找到所有 p 的字母异位词的起始索引std::vector<int> findAnagrams(std::string s, std::string p) {int n = p.length(); // p 的长度int m = s.length(); // s 的长度std::vector<int> ans; // 用于存储结果的向量// 如果 p 的长度大于 s 的长度，则不可能有异位词，直接返回空结果if (n > m) return ans;// 用于记录 s 和 p 中每个字符的频率std::vector<int> sCount(26, 0); // s 中字符的频率计数器std::vector<int> pCount(26, 0); // p 中字符的频率计数器// 初始化频率表，计算前 n 个字符的频率for (int i = 0; i < n; i++) {sCount[s[i] - 'a']++; // 统计 s 的前 n 个字符pCount[p[i] - 'a']++; // 统计 p 的所有字符}// 如果初始窗口匹配，记录起始位置if (sCount == pCount) ans.push_back(0);// 滑动窗口，遍历 s 中从 n 到 m 的字符for (int i = n; i < m; i++) {sCount[s[i] - 'a']++;        // 增加当前字符的频率sCount[s[i - n] - 'a']--;    // 减少窗口最左侧字符的频率// 如果当前窗口匹配，记录起始位置if (sCount == pCount) ans.push_back(i - n + 1);}return ans; // 返回所有找到的起始索引}
};