LeetCode 1358中等滑动窗口
包含所有三种字符的子字符串数目 图解题解
这道题到底在问什么
只含 a、b、c 的字符串 s,统计同时包含至少一个 a、一个 b、一个 c 的连续子串数量。
- 输入
- s="abcabc"
- 输出
- 10
- 输入
- s="aaacb"
- 输出
- 3
- 输入
- s="abc"
- 输出
- 1
最优解：一步一步想明白
- 3记住「右扩计数、三种齐全就一次加 n−right、再左缩」,下面每一格都在套它。
- 4这一行是字符串,只有 a、b、c 三种字母。窗口从空开始,右指针从左往右一格格扩,右边面板盯着窗口里 a、b、c 各有几个、答案 ans 怎么涨。
- 5右指针扩一格,把第 0 位 "a" 计入窗口。现在窗口里 a 有 1 个、b 有 0 个、c 有 0 个。还差至少一种,先不能计数,继续右扩。
- 6右边再吃一位,把第 1 位 "b" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 0 个。还差至少一种,先不能计数,继续右扩。
- 7右指针接着右移,把第 2 位 "c" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
- 8窗口 [0, 2] 三种齐全。关键一步:左端固定在 0,右端从 2 一直到末尾 5 的子串都含全 a、b、c,正好 6−2 = 4 个,一次性加进答案,累计 4。
- 9左指针右移一格,移出第 0 位 "a",它的计数减一。现在 a:0 b:1 c:1,已经缺了一种,这一轮累加结束,右指针继续往后扩。
- 10右端再纳一位,把第 3 位 "a" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
- 11窗口 [1, 3] 三种齐全。关键一步:左端固定在 1,右端从 3 一直到末尾 5 的子串都含全 a、b、c,正好 6−3 = 3 个,一次性加进答案,累计 7。
- 12左指针右移一格,移出第 1 位 "b",它的计数减一。现在 a:1 b:0 c:1,已经缺了一种,这一轮累加结束,右指针继续往后扩。
- 13右指针继续右扩,把第 4 位 "b" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
- 14窗口 [2, 4] 三种齐全。关键一步:左端固定在 2,右端从 4 一直到末尾 5 的子串都含全 a、b、c,正好 6−4 = 2 个,一次性加进答案,累计 9。
- 15左指针右移一格,移出第 2 位 "c",它的计数减一。现在 a:1 b:1 c:0,已经缺了一种,这一轮累加结束,右指针继续往后扩。
- 16右边再进一位,把第 5 位 "c" 计入窗口。现在窗口里 a 有 1 个、b 有 1 个、c 有 1 个。三种都齐了!下一步可以一次性数一批子串。
- 17窗口 [3, 5] 三种齐全。关键一步:左端固定在 3,右端从 5 一直到末尾 5 的子串都含全 a、b、c,正好 6−5 = 1 个,一次性加进答案,累计 10。
- 18左指针右移一格,移出第 3 位 "a",它的计数减一。现在 a:0 b:1 c:1,已经缺了一种,而右指针已经到末尾、没有字符可扩了,扫描到此结束。
- 19扫完全程,把每个齐全窗口贡献的「n−right」加起来,一共 10 个同时含 a、b、c 的子串。右、左指针各只走一遍,O(n)。
⚠️ 容易写错的地方
✗ 错：枚举所有子串逐个判定
✓ 对：滑动窗口 + 三计数
枚举是 O(n²) 甚至更慢，窗口复用计数是 O(n)
✗ 错：齐全时只加 1 个
✓ 对：齐全时一次加 n − right 个
左端固定、右端可延到末尾的子串都合法，是一整批不是一个
✗ 错：左缩后忘了重判是否仍齐全
✓ 对：while 循环里左缩后继续判断
缩掉一个后若还齐全，还能以更靠右的左端再数一批
完整代码（Python / C++ / Java）
Python
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 ansC++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int numberOfSubstrings(string s) {
vector<int> count(3);
int left = 0, ans = 0, n = s.size();
for (int right = 0; right < n; ++right) {
count[s[right] - 'a']++;
while (count[0] && count[1] && count[2]) {
ans += n - right;
count[s[left++] - 'a']--;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numberOfSubstrings(String s) {
int[] count = new int[3];
int left = 0, ans = 0, n = s.length();
for (int right = 0; right < n; right++) {
count[s.charAt(right) - 'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
ans += n - right;
count[s.charAt(left++) - 'a']--;
}
}
return ans;
}
}复杂度
时间
O(n)
左右指针各只前进一遍,每个字符进出窗口各一次
空间
O(1)
只用长度为 3 的计数和 left/ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 包含所有三种字符的子字符串数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用「左端固定、右端延到末尾」来数,就不重不漏?+
我们在每个齐全窗口处,以当前左端 left 为起点,数出「右端从 right 到 n−1」这一批子串;left 不断右移、right 不断右扩,每个合法子串都恰好被它的「最小右端点 + 当时左端」数到一次,所以不重不漏。
这题和「至多/恰好 K 个不同」类滑窗有什么联系?+
都是滑动窗口计数。本题要的是「至少齐全」,一旦齐全,右端可以无限向右延伸都合法,所以按 n − right 批量计数;而「恰好 K 个不同」不单调,得用 atMost(K) − atMost(K−1) 的差分技巧。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 包含所有三种字符的子字符串数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。