找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。
不考虑答案输出的顺序。
示例 1：
输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。
示例 2：
输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
起始索引等于 0 的子串是 "ab"，它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba"，它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab"，它是 "ab" 的异位词。
提示：
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写字母
滑动窗口-字母计数：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int n = s.size();
int m = p.size();
vector<int> ans;
if (n < m)
{
return ans;
}
vector<int> cntS(26, 0);
vector<int> cntP(26, 0);
for (int i = 0; i < m; i++)
{
cntS[s[i] - 'a']++;
cntP[p[i] - 'a']++;
}
if (cntS == cntP)
{
ans.push_back(0);
}
for (int right = m; right < n; right++)
{
cntS[s[right] - 'a']++;
cntS[s[right - m] - 'a']--;
if (cntS == cntP)
{
ans.push_back(right - m + 1);
}
}
return ans;
}
};
核心思想
这题的关键在于理解“异位词”的本质。
两个字符串互为异位词，说明它们只是字符顺序不同，但每个字符出现的次数完全一样。
例如：
"abc""cba""bac"
这几个字符串中：
'a'都出现1次'b'都出现1次'c'都出现1次
所以它们互为异位词。
因此，判断一个子串是不是 p 的异位词，不需要真的排序，也不需要逐个排列组合，只需要判断它和 p 的字符计数是否完全一致。
由于题目中只有小写字母，所以可以用长度为 26 的数组统计每个字母出现的次数。
为什么使用固定长度滑动窗口
假设 p 的长度是 m。
如果 s 中某个子串是 p 的异位词，那么这个子串必须满足两个条件：
- 长度等于
m - 每个字母出现次数和
p完全相同
所以我们只需要在 s 中检查所有长度为 m 的连续子串。
这正好适合使用滑动窗口。
窗口始终保持长度为 m：
- 先统计
s[0 ... m - 1] - 然后每次向右移动一格
- 新加入右边一个字符
- 删除左边离开窗口的一个字符
这样就可以在 O(1) 的更新成本下得到下一个窗口的字符计数。
窗口更新公式
假设当前窗口是：
s[i ... i + m - 1]
下一个窗口就是：
s[i + 1 ... i + m]
这两个窗口相比，只发生了两个变化：
s[i]离开窗口s[i + m]进入窗口
所以字符计数数组的更新就是：
cntS[s[i]]--
cntS[s[i + m]]++
代码中使用 right 表示新进入窗口的下标：
cntS[s[right] - 'a']++;
cntS[s[right - m] - 'a']--;
此时窗口的起始位置是：
right - m + 1
所以如果当前窗口和 p 的计数相同，就加入答案：
ans.push_back(right - m + 1);
为什么计数数组相同就一定是异位词
设 cntS 表示当前窗口中每个字母出现的次数，cntP 表示 p 中每个字母出现的次数。
如果：
cntS == cntP
说明对于任意字母 c，都有：
cntS[c] == cntP[c]
也就是说，当前窗口和 p 中每个字母出现次数都完全相同。
由于窗口长度固定为 p.length，并且所有字符都来自小写字母集合，所以当前窗口只是把 p 的字符重新排列了一下。
因此当前窗口一定是 p 的异位词。
反过来，如果当前窗口是 p 的异位词，那么它只是字符顺序和 p 不同，每个字符出现次数一定相同。
所以：
cntS == cntP
因此：
当前窗口是
p的异位词，当且仅当cntS == cntP。
正确性证明
我们证明算法返回的所有下标，正好是 s 中所有 p 的异位词子串的起始下标。
结论 1：算法加入答案的下标一定合法
算法只会在下面这个条件成立时加入答案：
if (cntS == cntP)
此时当前窗口长度一定是 m = p.length。
根据上面的证明，cntS == cntP 当且仅当当前窗口是 p 的异位词。
所以算法加入的每一个起始下标，都对应一个合法的异位词子串。
结论 2：所有合法下标都会被算法找到
任意一个合法答案，设它的起始下标是 i。
那么对应子串一定是：
s[i ... i + m - 1]
因为异位词长度必须和 p 相同。
算法的滑动窗口会从 s[0 ... m - 1] 开始，每次向右移动一格，依次检查：
s[0 ... m - 1]s[1 ... m]s[2 ... m + 1]- ...
s[n - m ... n - 1]
所以窗口一定会扫描到 s[i ... i + m - 1]。
当扫描到这个窗口时，因为它是 p 的异位词，所以 cntS == cntP，算法会把 i 加入答案。
因此所有合法下标都会被找到。
得出结论
由结论 1 可知，算法不会加入错误下标。
由结论 2 可知，算法不会漏掉正确下标。
所以算法返回的结果正确。
复杂度分析
设 n = s.length，m = p.length。
初始化两个计数数组需要遍历 p 和 s 的第一个窗口，时间复杂度是：
O(m)
之后滑动窗口最多移动 n - m 次。
每次移动只做：
- 一个字符加入窗口
- 一个字符离开窗口
- 比较两个长度为
26的数组
因为 26 是常数，所以每次检查可以看作 O(1)。
因此总时间复杂度是：
O(n)
额外使用了两个长度为 26 的计数数组，所以空间复杂度是：
`O(1)