算法-字符串-76.最小覆盖子串

一、题目

二、思路解析

        1.思路：

                滑动窗口！！！

        2.常用方法：

                无

        3.核心逻辑：

                1.特殊情况：s或t是否为空字符串

if(s==null||t==null)return "";

                2.声明一个字符数组——用于记录对应字符出现的次数；声明一个遍历cnt——记录t字符串中字符的种类数量；

char[]ch=new char[128];
int cnt=0;
//遍历字符串t
for(int i=0;i<t.length();i++){if(ch[t.charAt(i)]==0)cnt++;ch[t.charAt(i)]++;
}

                3. 遍历字符串s，窗口进行滑动；

                        a.窗口扩容，对当前字符所在的数组中的所记录的次数减一；判断当前字符所在的数组的记录次数是否为0，如果为0，cnt--（表示为已经覆盖了t字符串中对应的字符的一种）

                         b.当cnt==0时，表示已经包含了t中的所有字符；然后更新最小的覆盖子串长度

                        c.缩容，将起始位置向右移动

三、代码实现

class Solution {public String minWindow(String s, String t) {if(s==null||t==null)return "";char[]ch=new char[128];int cnt=0;for(int i=0;i<t.length();i++){if(ch[t.charAt(i)]==0)cnt++;ch[t.charAt(i)]++;}int resLeft=-1;int resRight=s.length();int left=0;for(int right=0;right<s.length();right++){ch[s.charAt(right)]--;if(ch[s.charAt(right)]==0)cnt--;while(cnt==0){if(resRight-resLeft>right-left){resLeft=left;resRight=right;}if(ch[s.charAt(left)]==0)cnt++;ch[s.charAt(left)]++;left++;}}return resLeft<0?"":s.substring(resLeft,resRight+1);}
}