寻找字符串中所有字母异位词 题目描述 给定一个字符串 s 和一个非空字符串 p ，在 s 中找出所有 p 的字母异位词的起始索引。字母异位词指字母相同，但排列不同的字符串。你可以假设字符串只包含小写英文字母。 示例 输入：s = "cbaebabacd", p = "abc" 输出：[ 0, 6 ] 解释：起始索引 0 对应的子串是 "cba"，是 "abc" 的字母异位词。索引 6 对应的子串是 "bac"，也是 "abc" 的字母异位词。 解题步骤详解 步骤1：问题理解与思路分析 我们需要在较长字符串 s 中，找到所有较短字符串 p 的字母异位词。关键点： 字母异位词：字符种类和数量完全相同，仅顺序不同。 只包含小写字母，因此可用长度为26的数组表示字符计数。 核心思路：在 s 上使用一个长度与 p 相同的滑动窗口，比较窗口内字符计数是否与 p 的字符计数一致。 为什么用哈希思想？ 我们可以将 p 的字符计数视为一个“哈希指纹”，窗口内子串的字符计数是另一个“指纹”。通过比较两个指纹是否相等，判断是否为字母异位词，无需关心顺序。 步骤2：数据结构选择 因为字符范围固定（26个小写字母），使用两个长度为26的整数数组： pCount ：记录 p 中每个字符的出现次数。 windowCount ：记录当前滑动窗口内每个字符的出现次数。 比较两个数组是否相等即可判断字母异位词。 步骤3：具体算法流程 如果 s 长度小于 p 长度，直接返回空列表。 初始化 pCount ： 遍历 p ，对每个字符 c ，执行 pCount[c - 'a']++ 。 初始化第一个窗口的 windowCount ： 遍历 s 的前 len(p) 个字符，同样更新 windowCount 。 比较第一个窗口的 windowCount 和 pCount ，如果相等，将索引0加入结果列表。 滑动窗口遍历剩余部分： 窗口从索引 i 到 i + len(p) - 1 ， i 从1开始直到 len(s) - len(p) 。 移除窗口左侧字符： windowCount[s[i-1] - 'a']-- 。 加入窗口右侧新字符： windowCount[s[i + len(p) - 1] - 'a']++ 。 比较 windowCount 和 pCount ，如果相等，将当前起始索引 i 加入结果。 返回结果列表。 步骤4：实例推演 以 s = "cbaebabacd", p = "abc" 为例： pCount: a→1, b→1, c→1, 其余0。 第一个窗口 "cba"： windowCount: a→1, b→1, c→1。 与 pCount 相等，记录索引0。 滑动窗口，i=1： 移除 s[ 0 ]='c'，windowCount中c减1。 加入 s[ 3 ]='e'，windowCount中e加1。 此时窗口 "bae" 计数为 a→1, b→1, e→1，不匹配。 继续滑动，直到 i=6： 窗口 "bac"，计数 a→1, b→1, c→1，匹配，记录索引6。 结果列表为 [ 0, 6 ]。 步骤5：复杂度与优化 时间复杂度：O(n)，n 为 s 长度。每个字符进入和离开窗口各一次，每次更新常数长度数组。 空间复杂度：O(1)，只使用了两个固定长度数组。 步骤6：关键点总结 利用字符计数数组作为哈希指纹，避免了对每个窗口排序（排序法为O(n·k log k)，k为p长度）。 滑动窗口更新时只调整两个字符的计数，保证高效。 适用于字符集有限的问题，若字符集较大可用哈希表替代数组。