Leetcode_hot100_t9
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 * 104s和p仅包含小写字母
核心方法：固定长度滑动窗口 + 数组计数抵消（替代字典，效率更高）
核心逻辑梳理
- 异位词的本质：子串与
p的字符种类完全相同、每种字符的出现次数完全相同（顺序无关），因此子串长度必须等于p的长度（这是前提，窗口长度固定为len(p)）。 - 计数抵消的核心：
- 先统计
p中所有字符的出现次数，将其存入计数数组并设为「负值」（相当于「需要抵消的目标」）。 - 再用滑动窗口遍历
s，窗口内的字符计数「加 1」，当计数数组所有值都归 0 时，说明窗口内字符与p完全匹配（异位词）。
- 先统计
- 固定窗口滑动规则：
- 初始化第一个窗口（
s的前len(p)个字符），完成初始计数抵消。 - 后续窗口整体向右滑动，移除窗口左侧离开的字符（计数减 1）、添加窗口右侧新增的字符（计数加 1），无需重新统计整个窗口，保证效率。
- 初始化第一个窗口（
- 优化点：用长度为 26 的数组（对应 26 个小写英文字母）替代字典，避免
KeyError，且数组访问 / 比较效率更高，是本题的最优选择（时间复杂度 O (n)，空间复杂度 O (1)）。 - 边界处理：若
s长度小于p长度，直接返回空列表（无有效子串）。
思路落地关键补充
- 你想的「全 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
