LC438
找到字符串中所有字母异位词
滑动窗口 · 定长可视化:滑动窗口在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。
时间 O(n)空间 O(1)
题目1 / 15
题目与输入建立输入、目标与算法心智
异位词长度一定等于 |p|=3,所以窗口是定长的
正在加载算法场景...
当前发生了什么
在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。
机器状态
定长窗口、模式串需求计数 need、窗口计数 win。
为什么正确
异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。
不变量
窗口宽度恒等于 |p|;窗口计数与 need 相等 ⇔ 该窗口是异位词。
面试怎么说
异位词长度固定等于 |p|,所以用定长滑动窗口:维护窗口字符计数,每滑一格进出各一个字符再和 need 比对,相等则记录左边界,O(n)。
人类输入
在 s="abab" 中找出所有 p="ab" 的字母异位词子串的起始下标。
机制
异位词长度必等于 |p|,所以用定长窗口;每右移一格进一个字符、出一个字符,再比对计数。
机器状态
定长窗口、模式串需求计数 need、窗口计数 win。
可观察结果
异位词起始下标为 [0,1,2]。
不变量
- · 窗口宽度恒等于 |p|;窗口计数与 need 相等 ⇔ 该窗口是异位词。
常见误区
- · 窗口未满时只装入不比较;比较只在窗口宽度等于 |p| 时进行。
迁移练习
- · LC242 有效字母异位词
- · LC3 无重复字符最长子串
面试怎么答
异位词长度固定等于 |p|,所以用定长滑动窗口:维护窗口字符计数,每滑一格进出各一个字符再和 need 比对,相等则记录左边界,O(n)。