LeetCode热题100：76. 最小覆盖子串

简介

题目链接：https://leetcode.cn/problems/minimum-window-substring/description/

解决方式：滑动窗口（双指针 + 数组）

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

推荐看灵茶山艾府大佬的讲解

滑动窗口（双数组）

classSolution{// 滑动窗口--双指针 + 数组// 双指针用来控制滑动窗口的大小和迭代元素// 数组用来存储特定的信息，作为双指针移动的依据publicStringminWindow(Strings,Stringt){// s 子串字符出现的次数int[]cntS=newint[128];// t 字符出现的次数int[]cntT=newint[128];// 遍历 t，将字符存进 cnt 方便后续对比for(inti=0;i<t.length();i++){cntT[t.charAt(i)]++;}// 初始化char[]str=s.toCharArray();intm=str.length;// 无效的初始状态intansLeft=-1;intansRight=m;// 最小覆盖子串的左右指针之所以这么设计，是为了方便后面没找到目标和首次找到目标时进行替换// 从头遍历 s，首先从 s 中找到涵盖 t 中字符的子串intleft=0;for(intright=0;right<m;right++){cntS[str[right]]++;// 如果找到了涵盖 t 字符的子串，那就进一步移动左指针找到最小的涵盖子串while(isCovered(cntS,cntT)){// 有两种情况// 第一种，刚从 s 中找到涵盖 t 的子串，需要进行赋值进而去找最小的子串// 由于之前 ansRight、ansLeft 的初始值（初始化长度）是无效的，即 m - (-1) = m + 1// 必定比找到的子串大，所以必然会重新赋值为最新的较小的子串// 第二种，已经找到了，但是在不断移动左指针找最小涵盖子串// 即当前子串为较小的子串，需要重新赋值if(right-left<ansRight-ansLeft){// 保存当前较小子串的位置，防止 left 移动丢之前的状态ansLeft=left;ansRight=right;}// 移动左指针，不断寻找是否有更小的子串cntS[str[left]]--;// 左端字母移出子串，防止涵盖判断出错left++;}}// 前面 ansLeft = -1 而不是 ansLeft = 0// 在此处就很好判断是否找到涵盖最小子串// 找到了就会被重新赋值不为 -1 没找到就不会重新赋值// 不会出现 0 是最小子串开头的索引还是标识没找到子串的二义性情况发生returnansLeft<0?"":s.substring(ansLeft,ansRight+1);}privatebooleanisCovered(int[]cntS,int[]cntT){for(inti='A';i<='Z';i++)if(cntS[i]<cntT[i])returnfalse;for(inti='a';i<='z';i++)if(cntS[i]<cntT[i])returnfalse;returntrue;}}

滑动窗口（单数组）

对判定涵盖的逻辑进行优化（less 变量）

classSolution{// 滑动窗口--双指针 + 数组// 对判定是否覆盖进行优化，使用一个数组 cnt 以 t 中的字符初始化// 新加 less 表示当前子串缺少的字符种类publicStringminWindow(StringS,Stringt){int[]cnt=newint[128];intless=0;for(charc:t.toCharArray()){// 刚开始数组中没有元素，先判断有没有 t 中的字符// 没有说明缺少该种字符需要计数// 后面即使有重复元素也不会进行重复计数if(cnt[c]==0){less++;}// 以 t 初始化数组cnt[c]++;}char[]s=S.toCharArray();intm=s.length;intansLeft=-1;intansRight=m;// 遍历 S 字符串，寻找最小涵盖子串intleft=0;for(intright=0;right<m;right++){// 移动子串右端点charc=s[right];// 右端点字母cnt[c]--;// 右端点字母移入子串if(cnt[c]==0){// 原来窗口内 c 的出现次数比 t 的少，现在一样多// 也就是说，当前子串不缺 t 种该种字符了less--;}// less 为零则表示当前子串涵盖 t 中所有字符了，需要移动左指针寻找最小子串// 寻找过程中不涵盖了就需要继续迭代 S 字符串中的剩下元素了// 以此来寻找最小的涵盖子串while(less==0){// 涵盖：所有字母的出现次数都是 >=if(right-left<ansRight-ansLeft){// 找到更短的子串ansLeft=left;// 记录此时的左右端点ansRight=right;}charx=s[left];// 左端点字母if(cnt[x]==0){// x 移出窗口之前，检查出现次数，// 如果窗口内 x 的出现次数和 t 一样，// 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少less++;}cnt[x]++;// 左端点字母移出子串left++;}}returnansLeft<0?"":S.substring(ansLeft,ansRight+1);}}