LeetCode 刷题笔记：如何用滑动窗口优雅解决“包含所有三种字符的子字符串”问题

最近在刷 LeetCode 的时候，遇到了一道非常典型的滑动窗口题目（第 1358 题）。这道题目虽然看起来简单，但如果思路不清，很容易写出 O(n^2) 甚至更高复杂度的代码，最后不仅超时，还容易被面试官问住。

今天我们就来详细拆解一下这道题，看看如何用“双指针”技巧优雅地搞定它。

题目描述

题目要求其实很直观：给你一个字符串 s，它里面只包含 a、b、c 这三种字符。你需要找出所有子字符串中，至少包含一个 a、一个 b 和一个 c 的子字符串个数。

LeetCode 1358 题目描述

LeetCode 1358 题目描述及示例

注意，子字符串是原字符串中连续的序列。哪怕内容一样，只要起始位置或结束位置不同，就算不同的子字符串。

示例分析

以 s = "abcabc" 为例，正确答案是 10。

大家可能会问，这 10 个是怎么来的？我们可以列出来看看：

abc
abca
abcab
abcabc
bca
bcab
bcabc
cab
cabc
abc (注意这是最后三个字符组成的，它和第 1 个虽然内容相同但位置不同)

如果用暴力法，两层循环遍历所有子串，再用一个哈希表或者数组统计字符出现情况，虽然对于短字符串可行，但一旦字符串变长，时间复杂度直接爆炸。

核心思路：滑动窗口（双指针）

滑动窗口双指针示意图

滑动窗口双指针移动示意图

这道题的精髓在于**“窗口取最小范围，以窗口左端点起始包含窗口的所有字符串都符合条件”**。

换句话说，当我们找到一个最小的窗口 [l, r]，这个窗口里已经包含了 a、b、c 各至少一个，那么以 l 开头，以 r 及 r 之后任意位置结尾的子字符串，一定也都符合条件！

这就避免了重复计算，把问题转化为了：每当我们找到一个合法窗口，就立刻计算它贡献了多少个答案，然后移动左指针缩小窗口。

算法步骤拆解

初始化：定义两个指针 l (左边界) 和 r (右边界)，初始都为 0。定义一个长度为 3 的数组 cnt，用来记录当前窗口内 a、b、c 的数量。
移动右指针：循环遍历字符串，r 不断向右移动。每移动一步，就把 chars[r] 对应的计数加 1。
检查窗口：当 cnt[0], cnt[1], cnt[2] 全部都大于 0 时，说明当前窗口 [l, r] 已经包含了三种字符。
统计答案：此时，对于固定的 l，只要子字符串的结尾在 r 或 r 之后（即 n-r 个位置），它都符合条件。所以，我们可以直接把 n - r 加到答案 ans 中。
收缩窗口：为了寻找下一个可能的突破口，我们移动左指针 l 向右一步，并把 chars[l] 对应的计数减 1，相当于把左边的字符踢出窗口。随后继续检查循环条件 while(...)，看看缩小后的窗口是否依然包含三种字符。如果依然包含，说明 l 刚才的新位置也能作为起始点，继续执行步骤 4 和 5。

代码实现 (Java)

理解了思路，代码就非常简洁了。

class Solution {
    public int numberOfSubstrings(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int l = 0;
        int[] cnt = new int[3]; // 记录 a, b, c 的数量
        int ans = 0;

for (int r = 0; r < n; r++) {
            // 右指针扩展窗口，加入当前字符
            cnt[chars[r] - 'a']++;

// 当窗口内同时包含 a, b, c 时
            while (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
                // 关键步骤：此时以 l 开头，r 及其之后结尾的子串都满足
                ans += n - r;

// 左指针收缩，尝试寻找下一个更小的窗口
                cnt[chars[l++] - 'a']--;
            }
        }

return ans;
    }
}

复杂度分析

时间复杂度：O(n)。虽然代码里有两层循环（一个 for，一个 while），但请注意，l 和 r 指针都只会从左向右移动，最多各移动 n 次。所以总的操作次数是线性的。
空间复杂度：O(1)。只用了几个变量和一个固定大小的数组，不随输入规模变化。

小结

这道题是练习滑动窗口的绝佳素材。它告诉我们，在处理“子串/子数组满足某种条件”的问题时，不要总是想着暴力遍历。试着维护一个动态的窗口，根据条件动态调整边界，往往能收到奇效。

如果你在面试中遇到这道题，写出这段代码并清晰地解释 ans += n - r 的含义，一定能给面试官留下“逻辑清晰、基础扎实”的好印象。