题目

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

实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.length() < p.length()) return {};

        int i = 0, j = p.length() - 1;
        array<int, 26> target{}, current{};

        // 计算p中每个字符的频率
        for (auto& c : p) target[c - 'a']++;

        // 初始化窗口，填充前p.length()个字符的频率
        for (int k = 0; k < j; k++) current[s[k] - 'a']++;

        vector<int> res;

        // 遍历s中的每个窗口
        while (j < s.size()) {
            current[s[j] - 'a']++;
            // 如果当前窗口的字符频率和目标一致，说明找到了一个异位词
            if (current == target) res.push_back(i);

            // 更新窗口
            // 移除左边界字符s[i]
            current[s[i] - 'a']--;
            // 增加右边界字符s[j + 1]
            i++;
            j++;
       }

        return res;
    }
};