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

难度：中等

题目描述

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

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

---

示例

示例 1:1

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

示例 2:2

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

---

提示:3

• 1 <= s.length, p.length <= 3 * 10^4

• s 和 p 仅包含小写字母

---

解题思路

这道题是“滑动窗口”算法的典型应用场景。核心思想是在字符串 s 上维护一个固定大小（与 p 的长度相同）的窗口，然后不断向右滑动这个窗口。在滑动的每一步，我们都检查窗口内的子串是否是 p 的一个异位词。

一个子串是 p 的异位词，等价于这个子串中所有字符的种类和数量与 p 完全一致。

直接的暴力解法是遍历 s 的所有长度为 p.length 的子串，然后对每个子串进行排序或计次来判断是否为异位词，但这样做效率太低。

滑动窗口算法的精髓在于，当窗口向右移动一格时，我们不需要重新统计整个窗口，而只需要进行增量更新：在窗口中增加右边新进入的字符，并移除左边滑出去的字符。这样可以将每次判断的复杂度从 O(p.length) 降为 O(1)。

为了高效地判断窗口内的字符构成是否符合要求，我们可以使用哈希表（或数组）来进行计数。

具体步骤如下：

1. 初始化需求列表 (need)：

   • 创建一个哈希表 need，用来统计目标字符串 p 中每个字符出现的次数。

2. 初始化滑动窗口 (window)：

   • 同样创建一个哈希表 window，用于统计当前在滑动窗口内的子串的字符频率。

   • 设置两个指针 left 和 right，初始都指向 s 的开头，表示窗口的左右边界。

   • 引入一个计数器 valid，用于记录当前 window 中有多少种字符的数量已经满足了 need 的要求。当 valid 的值等于 need 中不同字符的总数时，就意味着我们找到了一个异位词。

3. 滑动与判断：

   • 不断向右移动 right 指针，将 s[right] 纳入窗口，并更新 window 中的计数。

   • 如果 s[right] 是 p 中需要的字符，并且在加入后，它在 window 中的数量恰好等于在 need 中的数量，那么 valid 加一。

   • 当窗口的大小 (right - left) 达到 p.length 时，说明窗口已满，需要开始判断和收缩。

     • 判断：如果此时 valid 的值等于 need 中不同字符的总数，说明当前窗口内的子串是一个异位词，将 left 的值存入结果列表。

     • 收缩：将 left 指针右移一格，准备让窗口向右滑动。在移动前，需要更新 window 和 valid 的状态：如果即将移出窗口的字符 s[left] 是 p 所需的，并且它在 window 中的数量原本是“达标”的，那么在移出后 valid 就需要减一。同时，window 中对应字符的计数也减一。

4. 循环：重复第 3 步，直到 right 指针越过字符串 s 的末尾。

代码实现 (JavaScript)

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    // 最终返回的结果数组
    const result = [];
    // needMap 用于记录目标字符串 p 中需要的字符及其数量
    const needMap = new Map();
    // windowMap 用于记录当前滑动窗口中已有字符的数量
    const windowMap = new Map();

    // 1. 初始化 needMap
    for (const char of p) {
        needMap.set(char, (needMap.get(char) || 0) + 1);
    }

    // 记录 p 中不同字符的种类数，用于判断窗口是否满足条件
    const needSize = needMap.size;
    // validCount 用于记录当前窗口中，已经满足 needMap 数量要求的字符种类数
    let validCount = 0;
    // left 和 right 是滑动窗口的左右指针
    let left = 0, right = 0;

    // 2. 开始滑动窗口，right 指针负责扩大窗口
    while (right < s.length) {
        // c 是即将移入窗口的字符
        const c = s[right];
        right++;

        // 3. [窗口扩张] 更新窗口内数据
        // 如果 c 是 p 中需要的字符，则更新 windowMap 和 validCount
        if (needMap.has(c)) {
            windowMap.set(c, (windowMap.get(c) || 0) + 1);
            // 当窗口中 c 的数量等于 p 中需要的数量时，一个字符种类已满足要求
            if (windowMap.get(c) === needMap.get(c)) {
                validCount++;
            }
        }

        // 4. [窗口收缩] 判断是否需要收缩窗口
        // 当窗口大小 (right - left) 等于 p 的长度时，就需要判断并收缩
        while (right - left >= p.length) {
            
            // 4a. 检查当前窗口是否是异位词
            if (validCount === needSize) {
                result.push(left);
            }

            // d 是即将移出窗口的字符
            const d = s[left];
            left++;

            // 4b. [收缩更新] 如果移出的字符 d 是 p 中需要的，则需要更新 windowMap 和 validCount
            if (needMap.has(d)) {
                // 如果移出前，d 的数量正好是满足需求的数量，那么 validCount 需要减 1
                if (windowMap.get(d) === needMap.get(d)) {
                    validCount--;
                }
                // 窗口中 d 的数量减 1
                windowMap.set(d, windowMap.get(d) - 1);
            }
        }
    }

    return result;
};

复杂度分析

• 时间复杂度: O(L_s+L_p)，其中 L_s 是字符串 s 的长度，L_p 是字符串 p 的长度。我们首先需要 O(L_p) 的时间来构建 need 哈希表。之后，left 和 right 指针都各自最多遍历 s 一次，所以滑动窗口部分的时间复杂度是 O(L_s)。

• 空间复杂度: O(K)，其中 K 是字符集的数量。在这里，s 和 p 只包含小写字母，所以 K 是 26。needMap 和 windowMap 最多存储 K 个键值对。因此，空间复杂度可以看作是 O(1)。