LeetCode438. [M]找到字符串中所有字母异位词（滑动窗口）
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
思路
使用滑动窗口，主要分为两种，定长窗口和不定长窗口
代码
定长窗口
输入分别为s和p，我们需要找出s中所有p得字母异位词字串，定长窗口为窗口的长度等p得长度（np），我们从s得第一个字符开始移动窗口，判断窗口中的字符是否为p得字母异位词
判断方法：窗口中字串得字符出现种类及次数和p相同
代码如下
//定长窗口
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
//获取s和p得长度
int sn=s.size(),pn=p.size();
if(sn<pn) return {};
vector<int> ans;
//countp代表字符串p中每个字母出现的种类及次数
//counts代表字符串s当前窗口中每个字母出现得种类及次数
vector<int> countp(26,0);
vector<int> counts(26,0);
for(char c : p)
{
countp[c-'a']++;
}
for(int i=0;i<pn;i++)
{
counts[s[i]-'a']++;
}
if(countp==counts) ans.push_back(0);
//滑动窗口
for(int i=1;i<=sn-pn;i++)
{
//相当于将最左侧字符移出窗口
counts[s[i-1]-'a']--;
//将新的字符加入窗口
counts[s[i+pn-1]-'a']++;
//如果两个数组相同，代表当前窗口中的字串为p的字母异位词
if(counts==countp) ans.push_back(i);
}
return ans;
}
};复杂度
- 时间复杂度：O(∣Σ∣m+n)，其中 m 是 s 的长度，n 是 p 的长度，∣Σ∣\=26 是字符集合的大小。
- 空间复杂度：O(∣Σ∣)。返回值不计入。
为什么26个英文字母可以转换为0-25的int
每个字符在计算机中本质上都是一个整数（使用ASCII 码）：
-
'a' 的 ASCII 是 97 -
'b' 是 98，'c' 是 99，一直到'z' 是 122
故：
'a' - 'a' = 97 - 97 = 0
'b' - 'a' = 98 - 97 = 1
...
'z' - 'a' = 122 - 97 = 25不定长滑动窗口
不定长窗口使用一个数组，通过差值来判断窗口中的字串是否是p的字母异位词
即我们先使用count数组计算字符串p中每个字符的出现次数，不需要在使用另一个数组去进行对比，通过差值来进行判断。
- 计算p中字符出现的种类和数量
- 初始化left、right左右指针
移动right指针，将count中对应字符（s[right]）的出现次数减1，判断该字符的出现次数，此时的字符有两种可能：
我们展开说一下这一部分，此时的字符c有两种可能
c为p中不存在的字符：p中不存在的字符在count初始化后值为0
-
count[c-'a']=0：代表窗口中没有该字符，因为p中不存在的字符在count中的数值默认为0，如果窗口中存在该字符，值应为-1。 -
count[c-'a']<0：代表目前窗口中有p中不存在的字符，我们需要移动左指针，直到该字符滑出窗口。
-
c为p中存在的字符：p中存在的字符在count初始化后值为
[1,np](p中可能有重复的字符)。-
count[c-'a']>0：代表窗口中c的数量<p中c的数量，无法构成异位词，我们需要移动右指针，尝试增加窗口中c的数量 -
count[c-'a']=0：代表窗口中c的数量=p中c的数量 -
count[c-'a']<0：代表窗口中c的数量>p中c的数量,我们需要移动左指针，尝试减少窗口中c的数量，直到窗口中c的数量=p中c的数量
-
判断当前窗口中的字串是否为p的字母异位词，经过步骤3的一系列操作，我们始终保证窗口中
- 不会出现p中没有的字符
- 窗口中p中存在的字符<=p中该字符的数量
那么当窗口的长度等于p的长度的时候要想满足上述两个条件，只有窗口中只存在p中存在的字符且每个字符的数量相等这一种情况， 也就是此时窗口中的字串为p的字母异位词 。
//不定长窗口
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int sn=s.size(),pn=p.size();
if(sn<pn) return{};
int count[26]{};
vector<int> ans;
//局部变量必须初始化，否则数值为内存中的随机值
int left=0;
//计算p中字符出现的数量，未出现的字符数组中的值为0
for(char c: p)
{
count[c-'a']++;
}
//滑动右指针
for(int right=0;right<sn;right++)
{
//字符转化为int
int a=s[right]-'a';
//减少该字符的计数（代表窗口多了一个该字符）
count[a]--；
//当该字符出现次数小于0
//1.假设该字符为p中存在的字符，代表窗口中该字符的数量多于p，需要减少该字符数量
//2.假设该字符为p中不存在的字符，代表窗口中出现了p中没有的字符，更需要移除该字符。
while(count[a]<0)
{
//移除最左侧字符，注意恢复计数
count[s[left]-'a']++;
left++;
}
//添加结果
if(right-left+1==pn) ans.push_back(left);
}
return ans;
}
};复杂度
- 时间复杂度：O(m+n)，其中 m 是 s 的长度，n 是 p 的长度。虽然写了个二重循环，但是内层循环中对 left 加一的总执行次数不会超过 m 次，所以滑窗的时间复杂度为 O(m)。
- 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣=26 是字符集合的大小。返回值不计入。
为什么要用while而非if
以s为abbac，p为abc为例，当窗口中有ab时，此时窗口增加字符b，那么left需要++两次， 此时窗口中没有字符 ， 之后bac进入窗口，得到结果
对于不属于p的字符，只要进入一个就会导致其为负数，窗口必须将其移除，关键在于发生重复的字符不一定在窗口的最左侧
结语
笔者认为LeetCode43. 找到字符串中所有字母异位词的难度要高于LeetCode3. 无重复字符的最长子串，也让笔者对滑动窗口的理解更加深入，尤其对于不定长窗口和滑动窗口的优化两方面，每当笔者看到一个优秀的题解，总会遇到几个笔者想不明白的点，就比如本文在不定长窗口中着重介绍的为什么该方法可以保证得到正确的字母异位词以及为什么使用while而非if，笔者并不喜欢使用大量的文字描述一个简单的事情，当然，笔者的表达能力有限，可能还是会有些许繁琐。 对于这两个问题的解释也是笔者在研究过程中的理解，希望对大家有帮助，知其然，知其所以然。
参考
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）（灵茶山艾府）
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）（力扣官方题解）
本文介绍了两种滑动窗口方法解决LeetCode 438题「找到字符串中所有字母异位词」：
定长滑动窗口
- 窗口长度固定为p的长度，逐个移动窗口位置
- 用两个计数数组分别统计窗口内字符和p的字符频率
- 直接比较两个数组判断是否为异位词
- 时间复杂度O(26*(m-n))，空间复杂度O(26)
不定长滑动窗口
- 动态调整窗口边界，通过差值判断
- 单个计数数组记录p的字符频率，滑动时增减计数
- 利用正负值判断字符是否超出p的范围或数量
- 当窗口长度等于p长度时即为有效解
关键点：
- ASCII字符转0-25索引的技巧
- 两种方法都通过维护字符频率来高效判断异位词
- 定长窗口实现更简单，不定长窗口理论效率更高