当前位置：首页 > web >正文

专题二_滑动窗口_找到字符串中所有字母异位词

web 2025/8/11 23:46:22

一：题目

解释：比如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字符串存储进hash2hash2[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;}
};