【力扣hot100：76. 最小覆盖子串】

题目链接76. 最小覆盖子串思路这道题的目的是找s中最短窗口的子串这个子串要包含t中的所有字符这个题可以使用滑动窗口来做。题的难点在于如何判断当前s的窗口是否包含t中所有字符解决方式题目说明了s和t由英文字母组成所以我们可以创建cnt数组统计字符个数然后可以用枚举的方式来做判断。具体方式见下面的isCovered方法代码classSolution{publicStringminWindow(StringS,Stringt){/** * 找s中包含t的最短窗口 * 拆开1.判断是否包含 2.是否最短 *///创建统计s跟t的个数的数组int[]cntSnewint[128];int[]cntTnewint[128];//统计t的所有字母以及个数for(charc:t.toCharArray()){cntT[c];}char[]sS.toCharArray();intms.length;//滑动窗口枚举leftintansLeft-1;intansRightm;intleft0;for(intright0;rightm;right){cntS[s[right]];while(isCovered(cntS,cntT)){//查看当前的窗口是否更小if(right-leftansRight-ansLeft){ansRightright;ansLeftleft;}cntS[s[left]]--;left;}}returnansLeft0?:S.substring(ansLeft,ansRight1);}privatebooleanisCovered(int[]cntS,int[]cntT){for(intca;cz;c){if(cntS[c]cntT[c]){returnfalse;}}for(intcA;cZ;c){if(cntS[c]cntT[c]){returnfalse;}}returntrue;}}时间复杂度分析初始化cntT遍历符串t时间复杂度是O(n)for循环right循环执行m次时间复杂度是O(m)while循环当中left最多移动m次时间复杂度是O(m)isCovered方法遍历的是字符集A-Z, a-z共 52 次所以isCovered方法本身的复杂度是O(1)isCovered总调用次数最多是2m次所以总的时间复杂度是O(m)综上分析总的时间复杂度是O(mn)注意滑动窗口中两个指针各自单向遍历一次千万不要认为嵌套循环就一定是O(m^2)如果这篇文章对你有帮助欢迎点赞、评论、关注、收藏。你们的支持是我前进的动力