题目描述
思路解析动画文字版
记住「右扩计数、三种齐全就一次加 n−right、再左缩」,下面每一格都在套它。
这一行是字符串,只有 a、b、c 三种字母。窗口从空开始,右指针从左往右一格格扩,右边面板盯着窗口里 a、b、c 各有几个、答案 ans 怎么涨。
右指针扩一格,把第 0 位 "a" 计入窗口。现在窗口里 a 有 1 个、b 有 0 个、c 有 0 个。还差至少一种,先不能计数,继续右扩。
右边再吃一位,把第 1 位 "b" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 0 个。还差至少一种,先不能计数,继续右扩。
右指针接着右移,把第 2 位 "c" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
窗口 [0, 2] 三种齐全。关键一步:左端固定在 0,右端从 2 一直到末尾 5 的子串都含全 a、b、c,正好 6−2 = 4 个,一次性加进答案,累计 4。
左指针右移一格,移出第 0 位 "a",它的计数减一。现在 a:0 b:1 c:1,已经缺了一种,这一轮累加结束,右指针继续往后扩。
右端再纳一位,把第 3 位 "a" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
窗口 [1, 3] 三种齐全。关键一步:左端固定在 1,右端从 3 一直到末尾 5 的子串都含全 a、b、c,正好 6−3 = 3 个,一次性加进答案,累计 7。
左指针右移一格,移出第 1 位 "b",它的计数减一。现在 a:1 b:0 c:1,已经缺了一种,这一轮累加结束,右指针继续往后扩。
右指针继续右扩,把第 4 位 "b" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
窗口 [2, 4] 三种齐全。关键一步:左端固定在 2,右端从 4 一直到末尾 5 的子串都含全 a、b、c,正好 6−4 = 2 个,一次性加进答案,累计 9。
左指针右移一格,移出第 2 位 "c",它的计数减一。现在 a:1 b:1 c:0,已经缺了一种,这一轮累加结束,右指针继续往后扩。
右边再进一位,把第 5 位 "c" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
窗口 [3, 5] 三种齐全。关键一步:左端固定在 3,右端从 5 一直到末尾 5 的子串都含全 a、b、c,正好 6−5 = 1 个,一次性加进答案,累计 10。
左指针右移一格,移出第 3 位 "a",它的计数减一。现在 a:0 b:1 c:1,已经缺了一种,而右指针已经到末尾、没有字符可扩了,扫描到此结束。
扫完全程,把每个齐全窗口贡献的「n−right」加起来,一共 10 个同时含 a、b、c 的子串。右、左指针各只走一遍,O(n)。
边界先想清:长度小于 3 或缺某字符时为 0,整串齐全时至少 1 个。
面试常考:用「左端固定 + 右端延到末尾」论证不重不漏,以及与 atMost 差分类题的区别。
参考代码
class Solution: def numberOfSubstrings(self, s: str) -> int: count = [0, 0, 0] left = ans = 0 for right, ch in enumerate(s): count[ord(ch) - 97] += 1 while all(count): ans += len(s) - right count[ord(s[left]) - 97] -= 1 left += 1 return ans复杂度
- 时间：O(n)，左右指针各只前进一遍,每个字符进出窗口各一次
- 空间：O(1)，只用长度为 3 的计数和 left/ans 几个变量
易错点
面试追问把动画讲成自己的话
追问为什么用「左端固定、右端延到末尾」来数,就不重不漏?
追问这题和「至多/恰好 K 个不同」类滑窗有什么联系?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
可获得的最大点数
LeetCode 1423 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题