leetcode 1358 包含所有三种字符的子字符数目

一、问题描述二、解题思路解法一暴力枚举优化最容易想到的办法是使用2个for循环进行暴力枚举但是在这个基础上我们可以进行优化。固定子字符的起点若此时已经满足条件则后续字符无需再完成遍历直接用ret(s.size()-j)即可。解法二滑动窗口由于子数组连续且可以做到指针不回退所以可以使用滑动窗口来解决这个问题。三、代码实现解法一暴力枚举优化(超时)class Solution { public: int numberOfSubstrings(string s) { //暴力优化 int ret0; for(int i0;i!s.size();i){ mapchar,int hash; int count0; for(int ji;j!s.size();j){ char ins[j]; hash[in]; if(hash[in]1) count; if(count3) { ret(s.size()-j); break; } } } return ret; } };解法二滑动窗口class Solution { public: int numberOfSubstrings(string s) { //滑动窗口 mapchar,int hash;int count0; int ret0; for(int left0,right0;right!s.size()count!3;right){ //进窗口 char ins[right];hash[in]; if(hash[in]1) count; //出窗口 while(count3){ rets.size()-right; char outs[left]; hash[out]--; if(hash[out]0) count--; } } return ret; } };