XingHuiSamaの宝藏之地

给定两个字符串 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 * 104
s 和 p 仅包含小写字母

1. 算法核心思想：双频统计与定长滑动

寻找字母异位词的本质，是比对两个字符串中各个字符的出现频率是否完全一致，无需考虑字符的排列顺序。本解法采用定长滑动窗口配合双特征数组的策略：

特征数组：利用目标字符串仅包含小写字母的特性，开辟两个长度为 26 的 vector<int> 数组，分别记录目标串 p 和当前窗口 s 内的字符频率。底层的数组比对效率显著高于哈希表。
定长滑动：异位词的长度必须与目标串 p 绝对相等，因此窗口在初始化成型后，宽度固定。窗口向右滑动时，严格遵循“右侧新增一字符，左侧移出一字符”的同步操作。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;

        if (s.length() < p.length()) {
            return ans;
        }

        vector<int> pmap = vector<int>(26,0);
        vector<int> cmap = vector<int>(26,0);
        for (auto c : p) {
            pmap[c - 'a']++;
        }

        int len1 = p.length();
        int front = 0;
        int back = 0;

        for (int i = 0; i < len1; i++) {
            cmap[s[i] - 'a']++;
            back++;
        }

        if (cmap == pmap) {
            ans.push_back(0);
        }

        while (back < s.size()) {
            cmap[s[front] - 'a']--;
            front++;
            cmap[s[back] - 'a']++;
            back++;
            if (cmap == pmap) {
                ans.push_back(front);
            }
        }

        return ans;
    }
};

2. 代码执行流程

边界防御：首先验证源串 s 的长度是否小于目标串 p，若小于则直接返回空结果集，避免后续越界。
特征录入：遍历字符串 p，将其字符频率映射至 pmap 数组。
组装初始窗口：通过 for 循环将 s 的前 len1 个字符一次性读入 cmap 数组中，完成初始窗口的搭建，并使 back 指针停留在初始窗口右侧边缘的下一个位置。随后执行首次特征比对，若数组一致，则记录索引 0。
匀速滑动：在 while 循环中，每次执行四个同步动作：
1. 移出左侧老字符：cmap[s[front] - 'a']--
2. 左指针右移：front++
3. 纳入右侧新字符：cmap[s[back] - 'a']++
4. 右指针右移：back++ 完成更替后，直接利用 C++ 容器重载的 == 运算符对比 cmap 与 pmap。匹配成功时，此时的 front 指针已指向当前新窗口的起始位置，直接将其存入结果集。

3. 复杂度剖析

时间复杂度：O(N)。其中 N 为字符串 s 的长度。初始构建 pmap 和首个窗口耗时 O(M)（M 为 p 的长度）。滑动过程中，while 循环执行 N−M 次。每次循环内部的数组比对 cmap == pmap 均为 26 次常数级别的运算。整体时间开销随输入规模呈线性关系。
空间复杂度：O(1)。算法全程仅开辟了两个固定长度为 26 的整型数组 pmap 和 cmap，内存占用恒定。