好的，我们这次来详细讲解 LeetCode 第 438 题「找到字符串中所有字母异位词」。
这道题是经典的“滑动窗口 + 字符计数”的应用，我会从题目描述、思路分析、步骤拆解到代码实现，一步步带你理解。

1. 题目描述

题目链接：LeetCode 438 – Find All Anagrams in a String

题目描述：
给定两个字符串 s 和 p，要求在 s 中找到所有 p 的 字母异位词 的子串，返回这些子串的起始索引。

字母异位词（Anagram） 指字母相同，但排列不同的字符串。例如 "abc" 的异位词包括 "acb"、"bca"、"cab" 等。

示例：

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

注意：

• 字符串只包含小写英文字母
• s 和 p 的长度可能在 [1, 3×10^4] 范围

2. 思路分析

2.1 暴力法（不可行）

最直接的想法是：枚举 s 中所有长度为 len(p) 的子串，判断它和 p 是否是字母异位词。
判断方法：对子串和 p 分别排序，或者用长度为 26 的数组统计字符出现次数。
但这样时间复杂度是 O(n × m) 或 O(n × m log m)（n 为 s 长度，m 为 p 长度），在数据规模大时会超时。

2.2 滑动窗口法（最优）

因为异位词只关心字符频率，不关心顺序，所以可以用 固定长度的滑动窗口 在 s 上滑动，并实时维护窗口内字符计数，与 p 的字符计数比较。

核心步骤：

1. 统计 p 中每个字符的出现次数（长度为 26 的数组，pCount[ch]++）。
2. 在 s 上设置一个长度为 len(p) 的窗口，统计窗口内字符的出现次数（sWindowCount[ch]++）。
3. 比较 pCount 和 sWindowCount 是否相等，相等则记录窗口起始索引。
4. 窗口向右滑动一位：去掉左边出去的字符，加入右边新进入的字符，更新 sWindowCount，然后回到步骤 3 比较。

这样每个字符进入和离开窗口各一次，时间复杂度 O(n)。

3. 详细步骤拆解

我们以 s = "cbaebabacd", p = "abc" 为例。

3.1 初始化

• pLen = 3, sLen = 10
• 创建 pCount 数组（长度 26，初始为 0）：
  • pCount['a'-'a'] = 1
  • pCount['b'-'a'] = 1
  • pCount['c'-'a'] = 1
• 创建 sWindowCount 数组（长度 26，初始为 0）
• 结果列表 result = []

3.2 先处理第一个窗口（索引 0~2）

窗口包含字符：'c','b','a'

• sWindowCount['a']=1, sWindowCount['b']=1, sWindowCount['c']=1
• 比较 sWindowCount 与 pCount：完全相等 → 找到异位词，记录索引 0。
• result = [0]

3.3 滑动窗口到索引 1~3

• 移除左边 s[0]='c'：sWindowCount['c'] 从 1 变 0
• 加入右边 s[3]='e'：sWindowCount['e'] 从 0 变 1
• 现在窗口字符频率：a:1, b:1, e:1
  与 p 的 a:1, b:1, c:1 不同 → 不是异位词。

3.4 滑动窗口到索引 2~4

• 移除 s[1]='b'：b 从 1 变 0
• 加入 s[4]='b'：b 从 0 变 1
• 窗口字符：a:1, e:1, b:1（顺序无关） → 仍与 p 不同。

3.5 继续滑动直到索引 6~8

• 当窗口在索引 6~8 时，字符为 'b','a','c'
• 频率：a:1, b:1, c:1 → 与 p 相同 → 记录索引 6
• result = [0, 6]

继续直到窗口无法移动（右边界到达 s 末尾）。

4. 代码实现（Python）

def findAnagrams(s: str, p: str) -> List[int]:
    s_len, p_len = len(s), len(p)
    if s_len < p_len:
        return []
    
    p_count = [0] * 26
    s_window_count = [0] * 26
    
    # 统计 p 的字符频次，并初始化第一个窗口
    for ch in p:
        p_count[ord(ch) - ord('a')] += 1
    for i in range(p_len):
        s_window_count[ord(s[i]) - ord('a')] += 1
    
    result = []
    # 判断第一个窗口
    if p_count == s_window_count:
        result.append(0)
    
    # 滑动窗口：i 是窗口左边界
    for i in range(1, s_len - p_len + 1):
        # 移除左边出去的字符 s[i-1]
        left_char = s[i - 1]
        s_window_count[ord(left_char) - ord('a')] -= 1
        # 加入右边进入的字符 s[i + p_len - 1]
        right_char = s[i + p_len - 1]
        s_window_count[ord(right_char) - ord('a')] += 1
        
        if p_count == s_window_count:
            result.append(i)
    
    return result

5. 复杂度分析

• 时间复杂度：O(n)，n 为 s 的长度，每个字符进入和离开窗口各一次，比较数组是 O(26) = O(1)。
• 空间复杂度：O(1)，因为固定使用两个长度 26 的数组。

6. 优化点

• 上面代码每次比较整个 26 长度的数组，可以优化为只记录差异数（用一个变量 diff 记录当前窗口与 p 的不同字符个数），当 diff == 0 时表示匹配。这样可以避免 O(26) 的比较，但逻辑稍复杂。
• 不过 O(26) 是常数，所以实际已经足够高效。

这样，我们就完成了从题意理解、思路推导、步骤演示到代码实现的完整讲解。
希望这个逐步拆解的过程能帮助你彻底掌握这道「滑动窗口」经典题！