题目描述
思路解析动画文字版
核心就一句:窗口长度钉死等于 s1,滑动时「进的加一、出的减一」,每步比一下窗口里的字母个数和需求是否完全相同。
先搭起始窗口:把下标 0 到 0 的字母圈进来,目前窗口里有 {c:1}。继续往右凑够 2 个字母。
先搭起始窗口:把下标 0 到 1 的字母圈进来,目前窗口里有 {c:1,d:1}。窗口长度凑到 2 了,正好等于 s1 的长度。
起始窗口里是 {c:1,d:1},和需求 {a:1,b:1} 不一样,不是排列。窗口开始向右滑。
窗口准备向右滑一格。标红的下标 0(字母 c)马上要滑出窗口,绿色的下标 2(字母 e)马上要进窗口。
窗口滑到下标 1~2,里面是 {d:1,e:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 1(字母 d)马上要滑出窗口,绿色的下标 3(字母 c)马上要进窗口。
窗口滑到下标 2~3,里面是 {e:1,c:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 2(字母 e)马上要滑出窗口,绿色的下标 4(字母 d)马上要进窗口。
窗口滑到下标 3~4,里面是 {c:1,d:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 3(字母 c)马上要滑出窗口,绿色的下标 5(字母 c)马上要进窗口。
窗口滑到下标 4~5,里面是 {d:1,c:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 4(字母 d)马上要滑出窗口,绿色的下标 6(字母 e)马上要进窗口。
窗口滑到下标 5~6,里面是 {c:1,e:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 5(字母 c)马上要滑出窗口,绿色的下标 7(字母 d)马上要进窗口。
窗口滑到下标 6~7,里面是 {e:1,d:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 6(字母 e)马上要滑出窗口,绿色的下标 8(字母 b)马上要进窗口。
窗口滑到下标 7~8,里面是 {d:1,b:1},和需求 {a:1,b:1} 不一样,继续往右滑。
窗口准备向右滑一格。标红的下标 7(字母 d)马上要滑出窗口,绿色的下标 9(字母 a)马上要进窗口。
窗口滑到下标 8~9,里面是 {b:1,a:1},正好等于需求 {a:1,b:1}。命中排列,返回 true。
滑动过程里,高亮这一段连续子串的字母个数和 s1 完全一致,它就是 s1 的一个排列,最终答案 true。
三个高频追问:窗口为何定长、怎么快速比个数、为什么用计数数组而非每次重数。
参考代码
def checkInclusion(s1, s2): if len(s1) > len(s2): return False need = [0]*26 # s1 各字母需求 win = [0]*26 # 当前窗口各字母 for c in s1: need[ord(c)-97] += 1 k = len(s1) for i, c in enumerate(s2): win[ord(c)-97] += 1 # 进的 +1 if i >= k: # 超长了,左边滑出 win[ord(s2[i-k])-97] -= 1 # 出的 -1 if win == need: return True # 个数全相同 return False复杂度
- 时间:O(n),窗口在 s2 上滑一趟,每步只做一加一减加一次 26 长度的定长比较
- 空间:O(1),只用两个长度 26 的计数数组,和字符串长短无关
易错点
面试追问把动画讲成自己的话
追问为什么窗口长度可以固定?
追问怎么快速判断两个窗口的字母个数相同?
追问能不能不用 26 长度数组,每次都数一遍窗口?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
最小覆盖子串
LeetCode 76 · 困难 · 沿着 滑动窗口 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题