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 完全一致。

先连接上一单元：窗口仍在向右滑动，但“合法性”变成固定长度与频次一致Unit 05 → Unit 06
#3：可变长度合法窗口

窗口中不能出现重复字符。right 扩张；约束被破坏时，left 持续收缩，窗口长度会变化。

→
#438：固定长度频次窗口

候选长度由 len(p) 预先确定。窗口每次整体右移一格，只更新一个进入字符和一个离开字符。

真正迁移的是“连续区间＋增量维护状态”：#3 用 set 描述窗口是否合法；#438 用频次表描述窗口组成。先确定窗口表达什么，再决定何时收缩以及维护哪种状态。
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 字符串的排列

先认识新题，再判断哪些窗口状态可以直接复用。学习者尚未理解 #567 的输入、输出和示例之前，不进入代码迁移。

1. 认识 #567 原题
2. 对照收集与存在性
3. 映射四个语义变化
4. 拼装并运行判断过程
题目内容依据 LeetCode #567 官方题面整理 查看官方原题 ↗
567. 字符串的排列｜Permutation in String 难度：Medium｜Hash Table · Two Pointers · String · Sliding Window

题目要求

给定两个字符串 s1 和 s2，判断 s2 是否包含 s1 的某一种排列。换句话说，只要 s2 中存在一个连续子串，其字符频次与 s1 完全一致，就返回 True；否则返回 False。

class Solution: def checkInclusion(self, s1: str, s2: str) -> bool: # 存在任意一个排列子串时返回 True

约束

  • 1 ≤ len(s1), len(s2) ≤ 10⁴
  • s1 和 s2 只包含小写英文字母。

官方示例

s1 = "ab", s2 = "eidbaooo"
输出：True
解释：连续子串 "ba" 是 "ab" 的一种排列。
s1 = "ab", s2 = "eidboaoo"
输出：False
解释：不存在长度为2且包含一个a、一个b的连续子串。

返回目标

本题只询问“是否存在”，不要求返回匹配子串、起点下标或所有匹配位置。

连续子串排列必须完整出现在 s2 的某一段连续区间中。
长度固定候选窗口长度必然等于 len(s1)。
频次一致字符顺序可以不同，但每种字符的出现次数必须相同。
布尔返回找到任意一个匹配立即 True；全部扫描后仍没有则 False。

读题检查 1｜函数最终返回什么？

读题检查 2｜为什么 s1="ab"、s2="eidbaooo" 返回 True？

已经掌握：#438 找到所有字母异位词

窗口长度：len(p) 目标状态：Counter(p) 匹配条件：window_count == target_count 命中后：result.append(left) 扫描结束：return result

准备迁移：#567 字符串的排列

窗口长度：len(s1) 目标状态：Counter(s1) 匹配条件：window_count == target_count 命中后：return True 扫描结束：return False
完全复用固定窗口长度、Counter 目标频次、右字符加入、左字符离开以及频次比较。
只改目标#438 收集所有起点；#567 只判断是否存在，因此第一次命中就是最终答案。
从“枚举所有匹配窗口”迁移到“存在性判定” 搜索空间和窗口不变量没有变化。变化的是输出量词：#438 要求所有匹配，所以必须扫描到底；#567 只要求存在一个匹配，命中后即可提前结束。

下面哪句话最准确地描述了迁移幅度？

槽位 A｜什么情况可以在扫描前直接返回 False？

槽位 B｜目标频次应该由谁建立？

槽位 C｜什么时候当前窗口代表 s1 的一种排列？

槽位 D｜匹配时与扫描结束时分别返回什么？

为什么命中后可以立即返回？#567 的结果只有“存在”或“不存在”。一个匹配窗口已经足以证明存在，后续窗口不会改变这个事实。
复用的窗口骨架right 加入字符，窗口过长时移除 s2[left]，并维持长度为 len(s1)。
复用的状态表示两张 Counter 分别描述目标组成与当前窗口组成，完全相等即排列匹配。
唯一核心变化把 result.append(left) 改成 return True，并在循环结束后返回 False。

#438：收集所有匹配起点

target_count = Counter(p)
window_count = Counter()
result = []
...
if window_count == target_count:
    result.append(left)
return result

#567：判断是否存在排列

target_count = Counter(s1)
window_count = Counter()
...
if window_count == target_count:
    return True
return False
官方样例运行轨迹0/0
可选挑战：脱离槽位，独立重写完整代码

这一步不阻碍主流程。固定窗口和 Counter 骨架已经保留，只需要补回匹配返回和最终返回。

本单元形成的算法Skill

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

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