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

本文概览：本文以LeetCode经典题目"找到字符串中所有字母异位词"为例，从暴力解法入手，逐步优化到滑动窗口+差异计数解法，系统讲解如何通过只关注窗口进出字符对差异的影响，将时间复杂度从 O(nm) 优化到 O(n)

一、题目

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

二、题目分析

给定两个字符串 s 和 p，在 s 中找到所有 p 的字母异位词的起始索引

字母异位词：由相同字母重新排列组成的字符串，例如 "abc" 和 "bac" 互为字母异位词

目标：找到 s 中所有长度为 p.length() 的子串，该子串是 p 的字母异位词，返回这些子串的起始索引

核心问题：如何快速判断一个窗口内的字符是否与 p 的字符完全一致（不考虑顺序）

思路概览

Java实现代码如下

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length())
        return res;
    int[] count = new int[26];
    int length = p.length();
    int diff = 0;

    // 窗口和p的字符数量汇总
    for (int i = 0; i < length; i++) {
        count[s.charAt(i) - 'a']++;
        count[p.charAt(i) - 'a']--;
    }

    // 统计差异数
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0)
            diff++;
    }

    // 窗口初始化是否符合要求
    if (diff == 0)
        res.add(0);

    // 窗口移动
    for (int i = 1; i <= s.length() - length; i++) {
        // 判断即将出去的左字符
        int left = count[s.charAt(i - 1) - 'a'];
        if (left == 1)
            // 窗口多出的这个字符在p中不存在，差异即将消除，diff--
            diff--;
        else if (left == 0)
            // 窗口的这个字符原本和p刚好匹配，出去后差异增大，diff++
            diff++;
        count[s.charAt(i - 1) - 'a']--;

        // 判断即将进入的右字符
        int right = count[s.charAt(i + length - 1) - 'a'];
        if (right == 0)
            // 即将进入的字符原本和p刚好匹配，进入后差异增大，diff++
            diff++;
        else if (right == -1)
            // p中多出的这个字符在窗口中不存在，进入后差异消除，diff--
            diff--;
        count[s.charAt(i + length - 1) - 'a']++;

        if (diff == 0)
            res.add(i);
    }
    return res;
}

思路简要说明

固定窗口大小：窗口大小等于 p 的长度，在 s 上滑动
差异计数：用 count 数组记录窗口字符与 p 字符的数量差，用 diff 记录有多少种字符存在差异
只看进出字符：窗口每次滑动，左字符出去、右字符进来，只需判断这两个字符对 count 和 diff 的影响，无需重新遍历整个窗口

三、思路详解

暴力解法入手

最自然的想法是：枚举 s 中所有长度为 p.length() 的子串，对每个子串统计字符频率，与 p 的字符频率逐个比较，如果完全一致则记录起始索引

显然可以得出以下结论

时间复杂度：O(n × m)，其中 n 为 s 的长度，m 为 p 的长度。对每个子串都要遍历统计字符并比较
核心瓶颈：每次窗口滑动一位，就要重新统计整个窗口的字符频率并和 p 比较，但窗口只变化了两个字符（左边出去一个，右边进来一个），其余字符都没变，做了大量无效计算
关键思考：能否只关注窗口进出字符的变化，而不是每次都全量比较？

滑动窗口 + 差异计数解法

思路分析

暴力解法的问题在于：每次窗口滑动后，都要重新遍历整个窗口来统计字符频率，再和 p 比较。但窗口每次只移动一位，实际上只有一个字符出去、一个字符进来

我们的优化思路是：只在初始化时进行一次窗口和 p 的全量比较，然后想办法记住当前状态，后续只看窗口左字符出去和右字符进来会不会改变这个状态

具体来说：

用 count 数组记录差异：count[s.charAt(i)-'a']++ 记录窗口字符，count[p.charAt(i)-'a']-- 记录 p 字符。这样 count 中每个位置的含义是：窗口中该字符比 p 多了几个（正值）或少几个（负值）
用 diff 记录差异种数：遍历 count 数组，统计有多少个位置的值不为 0。每个不为 0 的位置代表一种差异——要么窗口多了一个 p 中没有的字符（count[i] = 1），要么 p 多了一个窗口中没有的字符（count[i] = -1）
窗口滑动时只看进出字符：当 diff == 0 时，说明窗口和 p 完全匹配。窗口滑动时，左字符出去、右字符进来，我们只需要判断这两个字符对 count 的影响会不会让某个位置的值变为 0（差异消除，diff--）或从 0 变为非 0（差异产生，diff++）

count 数组的含义

count 数组是整个算法的核心，它同时记录了窗口和 p 的字符信息：

count[i] > 0：窗口中字符 i 比 p 中多 count[i] 个
count[i] < 0：窗口中字符 i 比 p 中少 |count[i]| 个
count[i] = 0：窗口中字符 i 和 p 中一样多

当所有 count[i] == 0 时，窗口和 p 的字符完全一致，即 diff == 0

窗口滑动时如何更新 diff

窗口滑动一位，左字符 out 出去，右字符 in 进来。关键在于判断这两个字符对 count 的改变会不会影响 diff

左字符出去时（count[out] 即将减 1）：

count[out] == 1：出去前窗口比 p 多一个该字符，出去后 count[out] 变为 0，差异消除，diff--
count[out] == 0：出去前窗口和 p 的该字符刚好匹配，出去后 count[out] 变为 -1，差异产生，diff++
count[out] == -1：出去前 p 比窗口多一个该字符，出去后 count[out] 变为 -2，差异仍然存在但种类不变，diff 不变。因此代码中没有判断 == -1 的情况

右字符进来时（count[in] 即将加 1）：

count[in] == -1：进来前 p 比窗口多一个该字符，进来后 count[in] 变为 0，差异消除，diff--
count[in] == 0：进来前窗口和 p 的该字符刚好匹配，进来后 count[in] 变为 1，差异产生，diff++
count[in] == 1：进来前窗口比 p 多一个该字符，进来后 count[in] 变为 2，差异仍然存在但种类不变，diff 不变。因此代码中没有判断 == 1 的情况

举例说明

以 s = "cbaebabacd", p = "abc" 为例

初始化窗口 "cba"：

字符	a	b	c
窗口 +1	1	1	1
p -1	-1	-1	-1
count	0	0	0

count 全为 0，diff = 0，匹配！记录索引 0

窗口滑动到 "bae"：左字符 c 出去，右字符 e 进来

c 出去：count['c'] = 0，从 0 变为 -1，diff++，diff = 1
e 进来：count['e'] = 0，从 0 变为 1，diff++，diff = 2

diff = 2 ≠ 0，不匹配

窗口滑动到 "aeb"：左字符 b 出去，右字符 b 进来

b 出去：count['b'] = 0，从 0 变为 -1，diff++，diff = 3
b 进来：count['b'] = -1，从 -1 变为 0，diff--，diff = 2

diff = 2 ≠ 0，不匹配

继续滑动...直到窗口滑动到 "bac"：左字符 e 出去，右字符 c 进来

e 出去：count['e'] = 1，从 1 变为 0，diff--
c 进来：count['c'] = -1，从 -1 变为 0，diff--

diff = 0，匹配！记录索引 6

最终结果为 [0, 6]

时间复杂度：O(n)，初始化 O(m) + 遍历 count O(26) + 滑动 O(n)，总体为 O(n)
空间复杂度：O(1)，count 数组大小固定为 26