【LeetCode: 1358. 包含所有三种字符的子字符串数目 + 滑动窗口】

发布时间：2026/7/1 19:25:13

算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 滑动窗口 题目要求 核心逻辑拆解 测试案例分析 实现代码 关键原理说明为什么 cnt left 是对的 运行效率 思考 共勉 题目链接1358. 包含所有三种字符的子字符串数目⛲ 题目描述给你一个字符串 s 它只包含三种字符 a, b 和 c 。请你返回 ab 和 c 都 至少 出现过一次的子字符串数目。示例 1输入s “abcabc”输出10解释包含 ab 和 c 各至少一次的子字符串为 “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” 和 “abc” (相同字符串算多次)。示例 2输入s “aaacb”输出3解释包含 ab 和 c 各至少一次的子字符串为 “aaacb”, “aacb” 和 “acb” 。示例 3输入s “abc”输出1提示3 s.length 5 x 10^4s 只包含字符 ab 和 c 。 求解思路实现代码运行结果⚡ 滑动窗口 题目要求题目要求统计同时包含 a、b、c 三种字符的所有子串数量。核心技巧滑动窗口维护区间 [left, right]保证窗口不满足同时有 a/b/c通过 left 的值快速算出以 right 为右端点的合法子串总数。 核心逻辑拆解右指针 right 逐个遍历字符不断扩大右边界记录窗口内 a/b/c 的出现次数num[0],num[1],num[2]。只要当前窗口 [left,right] 三种字符齐全就不断右移 left、减少左侧字符计数直到窗口缺少至少一种字符。此时所有起点在0 ~ left-1、终点为 right 的子串一定都同时包含 a/b/c合法子串数量正好等于 left累加到结果 cnt。遍历完所有 right累加总和就是答案。 测试案例分析举个直观例子s “abcabc”right2字符 c进入 while 循环收缩 left 到 1cnt 1right3字符 a继续收缩 left到 2cnt 2right4字符 b收缩 left 到 3cnt 3right5字符 c收缩 left到 4cnt 4总和 1234 10和样例输出一致。 实现代码classSolution{publicintnumberOfSubstrings(Strings){intns.length();intcnt0;int[]numnewint[3];intleft0;for(intright0;rightn;right){num[s.charAt(right)-a];while(num[0]0num[1]0num[2]0){num[s.charAt(left)-a]--;}cntleft;}returncnt;}} 关键原理说明为什么 cnt left 是对的循环结束后窗口 [left, right] 一定不满足三种字符齐全。那么起点 0,1,…,left-1终点 right子串 s[0,right]、s[1,right]…s[left-1,right]这些子串都包含完整 a/b/c总共有 left 个。 运行效率时间复杂度 O (n)left 和 right 最多各自遍历字符串一次无嵌套多层循环。空间复杂度 O (1)仅固定长度 3的数组额外空间不随字符串长度变化。 思考求解方法:滑动窗口/双指针核心考察:利用滑动窗口统计满足字符频次条件的子串数量。思考:如果字符种类变成 k 种你的代码需要怎么灵活调整呢 共勉最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉