题目链接 · 灵神原题解（署名来源）

核心思路

设 $n$ 是 $p$ 的长度。本题有两种做法：

1. 定长滑窗。枚举 $s$ 的所有长为 $n$ 的子串 $t$，如果 $t$ 的每种字母的出现次数，和 $p$ 的每种字母的出现次数都相同，那么 $t$ 是 $p$ 的异位词。
2. 不定长滑窗。枚举子串 $t$ 的右端点，如果发现 $t$ 其中一种字母的出现次数大于 $p$ 的这种字母的出现次数，则增大 $t$ 的左端点（缩小窗口）。如果发现 $t$ 的长度等于 $p$ 的长度，则说明 $t$ 的每种字母的出现次数，和 $p$ 的每种字母的出现次数都相同（如果出现次数 $t$ 的小于 $p$ 的，不可能长度一样），那么 $t$ 是 $p$ 的异位词。

方法一：定长滑窗

原理请看【套路】教你解决定长滑窗！适用于所有定长滑窗题目！。

用滑动窗口枚举 $s$ 的所有长为 $n$ 的子串 $t$。在滑的同时，维护 $t$ 的每种字母的出现次数。

如果 $t$ 的每种字母的出现次数，和 $p$ 的每种字母的出现次数都相同，那么 $t$ 是 $p$ 的异位词，把 $t$ 左端点下标加入答案。

Python 解法1

# 请选择 Python3 提交代码，而不是 Python
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt_p = Counter(p)  # 统计 p 的每种字母的出现次数
        cnt_s = Counter()  # 统计 s 的长为 len(p) 的子串 t 的每种字母的出现次数
        ans = []

        for right, c in enumerate(s):
            cnt_s[c] += 1  # 右端点字母进入窗口

            left = right - len(p) + 1
            if left < 0:  # 窗口长度不足 len(p)
                continue

            if cnt_s == cnt_p:  # t 和 p 的每种字母的出现次数都相同
                ans.append(left)  # t 左端点下标加入答案

            cnt_s[s[left]] -= 1  # 左端点字母离开窗口

        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 统计 p 的每种字母的出现次数
        array<int, 26> cnt_p{}; 
        for (char c : p) {
            cnt_p[c - 'a']++;
        }

        vector<int> ans;
        array<int, 26> cnt_s{}; // 统计 s 的长为 p.size() 的子串 t 的每种字母的出现次数
        for (int right = 0; right < s.size(); right++) {
            cnt_s[s[right] - 'a']++; // 右端点字母进入窗口
            int left = right - p.size() + 1;
            if (left < 0) { // 窗口长度不足 p.size()
                continue;
            }
            if (cnt_s == cnt_p) { // t 和 p 的每种字母的出现次数都相同
                ans.push_back(left); // t 左端点下标加入答案
            }
            cnt_s[s[left] - 'a']--; // 左端点字母离开窗口
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(|\mathrm{\Sigma }|m+n)$，其中 $m$ 是 $s$ 的长度，$n$ 是 $p$ 的长度，$|\mathrm{\Sigma }|=26$ 是字符集合的大小。
• 空间复杂度：$\mathcal{O}(|\mathrm{\Sigma }|)$。返回值不计入。

注：可以优化到 $\mathcal{O}(m+n)$ 或者 $\mathcal{O}(m)$，做法见我的 76. 最小覆盖子串的题解。

方法二：不定长滑窗

前置知识：滑动窗口【基础算法精讲 03】。

枚举子串 $t$ 的右端点，如果发现 $t$ 其中一种字母的出现次数大于 $p$ 的这种字母的出现次数，则右移 $t$ 的左端点（缩小窗口）。如果发现 $t$ 的长度等于 $p$ 的长度，则说明 $t$ 的每种字母的出现次数，等于 $p$ 的每种字母的出现次数，即 $t$ 是 $p$ 的异位词。

证明：内层循环结束后，$t$ 的每种字母的出现次数，都小于等于 $p$ 的每种字母的出现次数。如果 $t$ 的其中一种字母的出现次数比 $p$ 的小，那么 $t$ 的长度必然小于 $p$ 的长度。所以只要 $t$ 的长度等于 $p$ 的长度，就说明 $t$ 的每种字母的出现次数，和 $p$ 的每种字母的出现次数都相同，$t$ 是 $p$ 的异位词，把 $t$ 左端点下标加入答案。

代码实现时，可以把 $\mathit{\text{cntS}}$ 和 $\mathit{\text{cntP}}$ 合并成一个 $\mathit{\text{cnt}}$：

• 对于 $p$ 的字母 $c$，把 $\mathit{\text{cnt}}[p]$ 加一。
• 对于 $t$ 的字母 $c$，把 $\mathit{\text{cnt}}[c]$ 减一。
• 如果 $\mathit{\text{cnt}}[c]<0$，说明窗口中的字母 $c$ 的个数比 $p$ 的多，右移左端点。

答疑

问：为什么内层循环只判断了字母 $c$ 的出现次数，而不是每种字母的出现次数？

答：如果字母 $c$ 进入窗口后，窗口不合法（某个 $\mathit{\text{cnt}}[x]<0$），那么罪魁祸首是谁？由于在之前的循环中，我们已经把窗口变成合法的了，所以只能是刚进入窗口的字母 $c$ 导致窗口不合法，其余字母都满足 $\mathit{\text{cnt}}[x]\ge 0$，所以只需判断字母 $c$ 的出现次数。

Python 解法3

# 请选择 Python3 提交代码，而不是 Python
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        cnt = Counter(p)  # 统计 p 的每种字母的出现次数
        ans = []

        left = 0
        for right, c in enumerate(s):
            cnt[c] -= 1  # 右端点字母进入窗口
            while cnt[c] < 0:  # 字母 c 太多了
                cnt[s[left]] += 1  # 左端点字母离开窗口
                left += 1
            if right - left + 1 == len(p):  # t 和 p 的每种字母的出现次数都相同（证明见上）
                ans.append(left)  # t 左端点下标加入答案

        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 统计 p 的每种字母的出现次数
        int cnt[26]{}; 
        for (char c : p) {
            cnt[c - 'a']++;
        }

        vector<int> ans;
        int left = 0;
        for (int right = 0; right < s.size(); right++) {
            int c = s[right] - 'a';
            cnt[c]--; // 右端点字母进入窗口
            while (cnt[c] < 0) { // 字母 c 太多了
                cnt[s[left] - 'a']++; // 左端点字母离开窗口
                left++; 
            }
            if (right - left + 1 == p.size()) { // t 和 p 的每种字母的出现次数都相同（证明见上）
                ans.push_back(left); // t 左端点下标加入答案
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(m+n)$，其中 $m$ 是 $s$ 的长度，$n$ 是 $p$ 的长度。虽然写了个二重循环，但是内层循环中对 $\mathit{\text{left}}$ 加一的总执行次数不会超过 $m$ 次，所以滑窗的时间复杂度为 $\mathcal{O}(m)$。
• 空间复杂度：$\mathcal{O}(|\mathrm{\Sigma }|)$，其中 $|\mathrm{\Sigma }|=26$ 是字符集合的大小。返回值不计入。

注：如果特判 $m<n$ 的情况（直接返回空列表），则时间复杂度为 $\mathcal{O}(m)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府