哈希算法题目：寻找所有字母异位词 题目描述 给定两个字符串 s 和 p ，你需要找到 s 中所有 p 的 字母异位词 的子串起始索引。字符串只包含小写英文字母。 字母异位词（Anagram）指的是字母相同，但排列不同的字符串。例如，"abc" 的字母异位词包括 "abc"、"acb"、"bac"、"bca"、"cab"、"cba"。 要求时间复杂度尽可能低。 示例 输入: s = "cbaebabacd", p = "abc" 输出: [ 0, 6 ] 解释: 起始索引 0 的子串 "cba" 是 "abc" 的字母异位词，起始索引 6 的子串 "bac" 是 "abc" 的字母异位词。 解题思路 本题的核心是：在 s 中寻找长度与 p 相同的子串，且子串中每个字符的出现次数与 p 完全相同。 暴力解法是枚举 s 中所有长度为 len(p) 的子串，分别统计字符频率并与 p 比较，但时间复杂度为 O(n* m)（n 为 s 长度，m 为 p 长度），效率低。 更优的方法是 滑动窗口 + 哈希表 ，将时间复杂度降为 O(n)。 步骤详解 步骤1：理解问题本质 因为只包含小写字母，字符种类有限（26个），我们可以用 固定长度的数组 作为哈希表，下标对应字母（如 'a' 对应 0，'b' 对应 1，...），值表示该字母还需匹配的次数。 先统计 p 中每个字符的出现次数，记在数组 need 中。 然后在 s 上维护一个长度固定为 len(p) 的滑动窗口，实时统计窗口内字符的出现情况，与 need 比较。 步骤2：数据结构选择 使用数组 count[26] 作为哈希表，记录当前窗口中各字符的“余额”： count[i] 正数表示该字符还缺多少，负数表示该字符多出多少。 变量 diff 记录当前窗口与 p 在字符频率上 不同 的字符种类数。当 diff == 0 时，窗口是 p 的字母异位词。 步骤3：初始化计数数组 遍历 p ，对每个字符 c ，执行 count[c - 'a']++ 。这表示 p 中该字符需要的数量。 同时， diff 初始为 p 中不同字符的种类数（注意：不是字符总数）。例如 p="aab"，则 count[ 'a']=2, count[ 'b']=1，不同字符是 'a' 和 'b'，所以 diff=2 。 步骤4：滑动窗口的过程 窗口在 s 上从左向右滑动，每次右移一位： 移入窗口的字符 s[i] ：将其在 count 中的值 减1 。 如果减1后该字符的 count 值 变为0 ，说明该字符从“不匹配”变为“匹配”， diff 减1。 如果减1后该字符的 count 值 从0变为-1 ，说明该字符从“匹配”变为“不匹配”（多出一个）， diff 加1。 移出窗口的字符 s[i - m] （m 是 p 的长度）：将其在 count 中的值 加1 。 类似地，如果加1后该字符的 count 值 变为0 ， diff 减1。 如果加1后该字符的 count 值 从0变为1 ， diff 加1。 每次窗口移动后，检查 diff 是否为0，如果为0，则当前窗口起始索引符合条件，加入结果列表。 步骤5：示例推演 以 s="cbaebabacd", p="abc" 为例： 初始化：遍历 p="abc"，得到 count[ a]=1, count[ b]=1, count[ c]=1，其他为0。不同字符种类有 a、b、c 三种， diff=3 。 窗口初始为空，先处理前 m 个字符（i 从 0 到 m-1）： i=0，字符 'c'：count[ 'c'] 减1 从1→0，变为0， diff 减1 变为2。 i=1，字符 'b'：count[ 'b'] 减1 从1→0，变为0， diff 减1 变为1。 i=2，字符 'a'：count[ 'a'] 减1 从1→0，变为0， diff 减1 变为0。此时 diff=0，记录索引 0。 继续滑动（i=3，字符 'e'）： 移入 'e'：count[ 'e'] 减1 从0→-1（从匹配变不匹配）， diff 加1 变为1。 移出窗口左边界字符 s[ 0]='c'：count[ 'c'] 加1 从0→1（从匹配变不匹配）， diff 加1 变为2。 继续滑动直到找到下一个 diff=0 的窗口（i=6 时，窗口 "bac" 与 p 字符频率相同），记录索引 6。 步骤6：算法复杂度 时间复杂度 O(n)：s 和 p 各遍历一次。 空间复杂度 O(1)：只用到了长度 26 的数组。 步骤7：关键点总结 用固定数组作为哈希表，比通用哈希表更高效。 diff 变量的引入避免了每次比较整个数组，只需在字符计数跨过0时更新 diff 。 滑动窗口一次遍历，每次操作是常数时间。 扩展思考 如果字符串包含 Unicode 字符，则需用真正的哈希表（如字典）代替数组，原理相同。 此方法是“统计型滑动窗口”的经典应用，类似问题可举一反三（如“最小覆盖子串”）。 通过以上步骤，你可以在 O(n) 时间内找到 s 中所有 p 的字母异位词的起始索引，且空间消耗极小。