0438. Find All Anagrams in a String =================================== 题目信息 -------- :题号: 0438 :难度: Medium :主题: 小写字符串、异位词、固定长度子串、起始下标 :原题: `LeetCode 0438 `_ :重点: 子串长度必须等于 ``p``、字符频次完全相同、返回所有零基起点、重叠结果也要保留 题目重述 -------- 给定两个只包含小写英文字母的字符串 ``s`` 和 ``p``,找出 ``s`` 中所有与 ``p`` 互为字母异位词的连续子串,并返回这些子串在 ``s`` 中的零基起始下标。 异位词必须与 ``p`` 长度相同,并且每种字符的出现次数完全一致,只允许排列顺序不同。``s.length`` 和 ``p.length`` 均位于 ``[1, 3 * 10^4]``。合法子串可以彼此重叠;若 ``p`` 比 ``s`` 长,返回空数组。结果按扫描顺序自然递增。 自建示例 -------- 唯一异位词位于末尾: .. code-block:: text 输入:s = "baaacb",p = "abc" 输出:[3] 解释:从下标 3 开始的子串 acb 与 abc 的字符频次相同;其他长度为 3 的子串均不匹配。 重叠的异位词: .. code-block:: text 输入:s = "aaaa",p = "aa" 输出:[0,1,2] 解释:三个长度为 2 的窗口都由两个 a 组成,即使它们互相重叠,也必须分别返回起点。 固定窗口维护字符频次差 ------------------------ 异位词窗口长度必须等于 ``p``。先记录 ``p`` 的需求频次,右指针加入字符,窗口超过长度时左指针移出字符;维护尚未满足的字符实例数 ``missing``,当它变为 0 时当前窗口频次恰好与 ``p`` 相同,记录左端下标。窗口每次只移动一格,因此重叠结果不会被跳过。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector findAnagrams(std::string s, std::string p) { if (p.size() > s.size()) return {}; std::array need{}; std::array window{}; for (char c : p) ++need[c - 'a']; int missing = static_cast(p.size()); std::vector result; for (int right = 0; right < static_cast(s.size()); ++right) { int id = s[right] - 'a'; if (window[id] < need[id]) --missing; ++window[id]; if (right >= static_cast(p.size())) { int leftId = s[right - p.size()] - 'a'; if (window[leftId] <= need[leftId]) ++missing; --window[leftId]; } if (missing == 0) { result.push_back(right - static_cast(p.size()) + 1); } } return result; } }; 代码分析 -------- 加入字符只在它尚未超过需求时减少 ``missing``,移出字符只在它原本满足需求时恢复 ``missing``;窗口长度固定后,``missing == 0`` 等价于两组频次完全相同。时间复杂度为 ``O(|s| + |p|)``,额外空间为固定的 ``O(1)``。