Python算法训练序列

双指针与滑动窗口 · Unit 06

← Unit 05
438
LeetCode 438Find All Anagrams in a String

窗口长度固定，
每次只更新进入和离开的字符。

字母异位词不要求字符顺序相同，只要求字符频次完全一致。由于候选子串长度必须等于 len(p)，窗口每次右移一格时，只需加入一个新字符并移除一个旧字符。

LeetCode #438 原题内容中文转述 · 示例、约束与提交签名

题目要求

给定字符串 s 和 p，找到 s 中所有是 p 的字母异位词的子串，并返回这些子串的起始下标。答案顺序不限。

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: # 返回所有匹配窗口的起始下标

约束

  • 1 ≤ len(s), len(p) ≤ 30000
  • s 和 p 只包含小写英文字母。

示例

s = "cbaebabacd", p = "abc"
输出：[0,6]
"cba"与"bac"都是"abc"的异位词
s = "abab", p = "ab"
输出：[0,1,2]

核心条件

候选窗口长度必须等于 len(p)，且其中每个字符的出现次数与 p 完全一致。

1. 理解异位词
2. 体验重复统计
3. 建立固定窗口
4. 代码联动
5. 是否存在迁移
s = "cbaebabacd"，p = "abc"等待操作
当前固定长度窗口 s[left:right+1]
c

目标频次 target_count

窗口频次 window_count

已经记录的起始下标
result = []

当前循环不变量

进入匹配判断时，窗口长度恰好为 len(p)，且window_count准确描述窗口频次。

当前移动规则

right加入新字符；窗口过长时移除s[left]并右移left；长度正确时比较两张频次表。

left0
right0
窗口长度1
频次匹配否
结果数量0
为每个起点重新统计的瓶颈

若每个长度为m的子串都重新构造频次表，最坏需要检查约n个窗口，每个窗口又统计m个字符，复杂度约为O(nm)。相邻窗口实际上只有一个字符离开、一个字符进入。

补全 LeetCode 提交代码Counter固定窗口版本
from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
if len(p) > len(s):
return []
target_count =
window_count = Counter()
result = []
left = 0
for right, char in enumerate(s):
if right - left + 1 > len(p):
left_char = s[left]
if window_count[left_char] == 0:
del window_count[left_char]
left += 1
if :
return result
from collections import Counter class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: if len(p) > len(s): return [] target_count = Counter(p) window_count = Counter() result = [] left = 0 for right, char in enumerate(s): window_count[char] += 1 if right - left + 1 > len(p): left_char = s[left] window_count[left_char] -= 1 if window_count[left_char] == 0: del window_count[left_char] left += 1 if ( right - left + 1 == len(p) and window_count == target_count ): result.append(left) return result
为何删除频次为0的键？Counter比较会考虑键值状态。删除已经离开窗口且频次归零的字符，可以让window_count准确表示当前窗口，也让可视化和逻辑更清晰。
代码—窗口—频次表联动轨迹：cbaebabacd / abc
1from collections import Counter
3class Solution:
4 def findAnagrams(self, s: str, p: str) -> List[int]:
7 target_count = Counter(p)
8 window_count = Counter()
10 left = 0
11 for right, char in enumerate(s):
12 window_count[char] += 1
14 if right - left + 1 > len(p):
16 window_count[left_char] -= 1
20 left += 1
22 if window length == len(p) and counts equal:
26 result.append(left)
28 return result
逐行播放，观察窗口cba命中后如何滑到bae，再滑到第二个命中bac。
完成代码联动后进入“是否存在排列”迁移补全正确、查看答案或播放完整轨迹后解锁。

迁移题：LeetCode #567 字符串的排列

固定窗口和频次维护完全相同，只把“收集所有起点”改为“发现任意一个匹配窗口时立即返回True；扫描结束仍未匹配则返回False”。

本单元形成的算法Skill

当候选连续区间长度固定、判断条件依赖元素组成时，使用固定长度滑动窗口。每次右移只更新两个差异：新字符进入、旧字符离开；窗口长度正确后再比较状态，而不是重新统计整段。

LeetCode #438固定长度窗口Counter频次进入/离开更新返回所有起点O(n)
#167单调排除
#15锚点和去重
#3可变合法窗口
#438 当前固定频次窗口
#209 下一单元满足后持续收缩