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

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：哈希表、字符串、滑动窗口

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

字母异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2：

输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

---

2. 解题思路拆解

方法：滑动窗口 + 数组哈希

这道题可以看作是“固定长度的滑动窗口”。我们需要在 s 中维护一个长度为 p.length 的窗口，并判断这个窗口内的字符统计是否与 p 的字符统计完全一致。

1. 字符统计：因为只包含小写字母，我们可以使用长度为 26 的整数数组 need 来统计 p 中每个字符出现的次数。
2. 初始化窗口：
   • 先统计 p 的字符到 need 数组中。
   • 再维护一个 window 数组，统计 s 中前 p.length 个字符。
   • 如果 need 和 window 数组完全一样，说明找到了一个异位词，记录索引 0。
3. 滑动窗口：
   • 让窗口向右滑动（left 和 right 同时 +1）。
   • 入窗：s[right] 进入窗口，window 对应字符计数 +1。
   • 出窗：s[left] 离开窗口，window 对应字符计数 -1。
   • 检查：每次移动后，检查 need 和 window 数组是否相同。如果相同，记录当前的 left 索引。

优化技巧： 比较两个长度为 26 的数组虽然很快，但每次都比一遍还是有点冗余。我们可以维护一个变量 valid，表示窗口中已经有多少种字符的数量满足了要求。不过对于 26 个字母来说，直接比较数组开销非常小，写起来也最清晰。

---

3. 代码实现

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const sLen = s.length;
    const pLen = p.length;
    const ans = [];

    if (sLen < pLen) return ans;

    // 1. 初始化计数数组 (a-z -> 0-25)
    const sCount = new Array(26).fill(0);
    const pCount = new Array(26).fill(0);
    const base = 'a'.charCodeAt(0);

    // 2. 统计 p 的字符和 s 的第一个窗口
    for (let i = 0; i < pLen; i++) {
        pCount[p.charCodeAt(i) - base]++;
        sCount[s.charCodeAt(i) - base]++;
    }

    // 3. 检查第一个窗口
    if (sCount.toString() === pCount.toString()) {
        ans.push(0);
    }

    // 4. 开始滑动窗口
    for (let i = 0; i < sLen - pLen; i++) {
        // 出窗字符：s[i]
        sCount[s.charCodeAt(i) - base]--;
        
        // 入窗字符：s[i + pLen]
        sCount[s.charCodeAt(i + pLen) - base]++;

        // 检查当前窗口 (i + 1 为起始位置)
        // Array.toString() 会将数组转为逗号分隔的字符串，可以用来比较内容
        if (sCount.toString() === pCount.toString()) {
            ans.push(i + 1);
        }
    }

    return ans;
};

代码执行演示

输入 s = "cbaebabacd", p = "abc"

1. 初始化：
   • pCount (abc): [1, 1, 1, ...]
   • sCount (cba): [1, 1, 1, ...]
   • 比较相同 -> ans = [0]
2. 滑动 i=0：
   • 出窗 s[0] 'c' -> sCount 的 'c' 减 1。
   • 入窗 s[3] 'e' -> sCount 的 'e' 加 1。
   • 当前窗口 (bae): [1, 1, 0, 0, 1, ...] vs [1, 1, 1, ...] -> 不同。
3. 滑动 i=1：
   • 出窗 s[1] 'b'。入窗 s[4] 'b'。
   • 当前窗口 (aeb): 不同。
4. ...
5. 滑动 i=5：
   • 窗口变为 bac。
   • sCount (bac): [1, 1, 1, ...] vs pCount -> 相同。
   • ans.push(5 + 1 = 6)。
6. 最终返回 [0, 6]。

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。其中 $n$ 是字符串 s 的长度。虽然每次比较需要 $O(26)$，但这是一个常数，所以总体是线性的。
空间复杂度	$O(1)$。只需要两个长度为 26 的常数级数组。