LeetCode 力扣 热题 100道（二十三）找到字符串中所有字母异位词（C++）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

字母异位词，字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

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

        // 记录 p 的字符频率
        vector<int> pCount(26, 0), sCount(26, 0);
        for (char c : p) {
            pCount[c - 'a']++;
        }

        // 初始化 s 中的滑动窗口
        for (int i = 0; i < p.size(); ++i) {
            sCount[s[i] - 'a']++;
        }

        // 检查初始窗口是否匹配
        if (sCount == pCount) {
            result.push_back(0);
        }

        // 滑动窗口遍历 s
        for (int i = p.size(); i < s.size(); ++i) {
            // 添加右侧字符
            sCount[s[i] - 'a']++;
            // 移除左侧字符
            sCount[s[i - p.size()] - 'a']--;
            
            // 检查当前窗口是否匹配
            if (sCount == pCount) {
                result.push_back(i - p.size() + 1);
            }
        }

        return result;
    }
};

使用一个固定大小的窗口遍历字符串 s。

在每一步中，检查窗口内的字符计数是否与字符串 p 的字符计数匹配。

如果匹配，则记录当前窗口的起始索引。

使用两个计数器来高效地更新滑动窗口，避免重复计算。

字符计数：pCount 和 sCount 用于存储 p 和当前窗口的字符频率。每个频率数组大小为 26（对应字母 a-z）。

初始窗口设置：初始化 sCount 为 s 中前 p.size() 个字符的频率。

滑动窗口更新：

每次窗口向右滑动一个字符。

添加新字符到窗口中，同时移除窗口最左边的字符。

窗口匹配检查：每次更新窗口后检查 sCount 是否等于 pCount，相等时记录窗口的起始索引。