438. 找到字符串中所有字母异位词
给定两个字符串 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" 的异位词。
提示:
- 1 <= s.length, p.length <= 3 * 104
- s 和 p 仅包含小写字母
核心方法：固定长度滑动窗口 + 数组计数抵消（替代字典，效率更高）
核心逻辑梳理
- 先统计 p 中所有字符的出现次数，将其存入计数数组并设为「负值」（相当于「需要抵消的目标」）。
- 再用滑动窗口遍历 s，窗口内的字符计数「加 1」，当计数数组所有值都归 0 时，说明窗口内字符与 p 完全匹配（异位词）。
- 初始化第一个窗口（s 的前 len(p) 个字符），完成初始计数抵消。
- 后续窗口整体向右滑动，移除窗口左侧离开的字符（计数减 1）、添加窗口右侧新增的字符（计数加 1），无需重新统计整个窗口，保证效率。
思路落地关键补充
- 你想的「全 0 时记录 left」完全正确，数组格式下直接用 count == [0] * 26 即可快速判断。
- 遇到不属于 p 的字符时，无需额外跳转（数组天然只统计 26 个字母，且窗口固定长度，滑动时会自动清除无效字符的计数影响），简化逻辑。
from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
s_len = len(s)
p_len = len(p)
# 边界条件：如果 s 长度小于 p 长度，直接返回空列表
if s_len < p_len:
return result
# 初始化 26 个小写英文字母的计数数组（对应 a-z）
count = [0] * 26
# 步骤 1：统计 p 的字符，设为负值（贴合你的计数抵消思路）
for c in p:
idx = ord(c) – ord('a')
count[idx] -= 1
# 步骤 2：初始化第一个窗口（s 的前 p_len 个字符），计数累加抵消
for i in range(p_len):
idx = ord(s[i]) – ord('a')
count[idx] += 1
# 步骤 3：滑动窗口遍历所有可能的起始位置
for i in range(s_len – p_len + 1):
# 修正错误 1：数组和全 0 数组比较（正确判断计数是否全 0）
if count == [0] * 26:
result.append(i)
# 边界条件：如果是最后一个窗口，无需滑动（避免索引越界）
if i == s_len – p_len:
break
# 步骤 4：滑动窗口：移除左侧字符，添加右侧新字符
# 移除当前窗口的左侧字符 s[i]
left_char_idx = ord(s[i]) – ord('a')
count[left_char_idx] -= 1
# 修正错误 2：添加下一个窗口的右侧字符 s[i+p_len]（而非 i+p_len-1）
right_char_idx = ord(s[i + p_len]) – ord('a')
count[right_char_idx] += 1
return result
