438. 找到字符串中所有字母异位词

难度：🟡 Medium | 标签：滑动窗口、哈希、字符串 | 状态：⬜ LeetCode 链接

思路

固定长度滑窗（窗口大小 = p.size()），用 26 长计数数组比较。 每次窗口右滑：右端加入、左端弹出，O(26) 判断是否相等。

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size(), m = p.size();
        vector<int> res;
        if (n < m) return res;
        int cs[26] = {}, cp[26] = {};
        for (int i = 0; i < m; ++i) {
            cs[s[i] - 'a']++;
            cp[p[i] - 'a']++;
        }
        auto eq = [&] { return memcmp(cs, cp, sizeof cs) == 0; };
        if (eq()) res.push_back(0);
        for (int r = m; r < n; ++r) {
            cs[s[r] - 'a']++;
            cs[s[r - m] - 'a']--;
            if (eq()) res.push_back(r - m + 1);
        }
        return res;
    }
};

复杂度

• 时间 O(n · 26) = O(n)，空间 O(1)

易错 / 回顾

• 窗口长度固定 = p.size()，不能像变长滑窗那样动左
• memcmp 比手写循环更快
• 不要逐次重新统计窗口，必须增量更新