leetcode-76.最小覆盖子串

题目

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例输入输出

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

解题思路

我们需要在S中找到包含T所有字符的最小子串。最容易想到的解法就是，我们只需要对每一个区间进行遍历，如果包含的话统计一下，最后返回最小的字符串就是我们的答案。

for(int i = 0; i < s.length(); i++）{
    for(int j = i + 1; i < s.length(); j++){
          if(i 到 j的范围包含子串，进行比较){
              ······  
          }
    }
}

当然，这样的时间复杂度太高了。一般像类似这种的子串问题，我们一般都是用滑动窗口，既然是滑动窗口就少不了左右指针。我们就以示例的输入和输出为例，简单过一下流程。
（1）我们定义一个左指针和右指针；
（2）首先我们将我们的右指针进行向右滑动，在右指针到了第一个C的位置

（3）这个时候我们的左指针还是在初始位置，两个指针的区间就是包含我们子串的一个字符串，我们对其进行统计了。然后我们开始移动左指针，只要满足不包含我们的子串就可以了。所以左指针会在第一个D的位置

(4)现在区间是不包含子串的，所以我们就需要移动右指针，继续找包含我们子串的位置。我们直接展示后面所有的情况



（需要注意的是，我们在满足包含子串并且移动left指针的时候，是需要统计长度选取包含的最小的字符串）
所以我们在下面移动left的时候最后虽然是在A位置停止了，但是在B的时候，我们其实已经统计了。所以统计出来的结果就是BANC

我们最后的停止位置是在

下面给出代码

class Solution {
    public String minWindow(String s, String t) {
       if(s == null) return "";
       if(t == null) return t;
       int slen = s.length(),tlen = t.length();
       if(slen < tlen) return "";
       //定义左右指针和用来统计字符串重合的数量标记,以及比较字符串长度的max
       int left = 0,right = right = 0,cnt = 0,max = -1;
       //定义返回字符串，用来统计最短的子字符串
       String res = "";
       //我们定义一个哈希数组，用来统计子字符串的字符
       int[] mp = new int[256];
       for(char c : t.toCharArray()) mp[c] += 1;
       while(right < slen){
           char c = s.charAt(right);
           mp[c] -= 1;
           //如果满足了我们所需要的最小的字符串，统计次数加一，如果小于零说明多了我们不进行统计
           if(mp[c] >= 0) cnt += 1;
           //如果我们统计的次数刚好和我们的子字符串的长度相等的话，就是一个正确答案，我们记录并把状态移到不满足的下一个状态
           while(cnt == tlen){
               //如果是第一次或者是出现满足情况的更小的字符串，我们进行更新
               if(max == -1 || (right - left + 1) < max){
                   res = s.substring(left,right + 1);
                   max = right - left + 1;
               }
               c = s.charAt(left);
               //我们要制造不满足的情况，所以将之前舍掉的统计回来
               mp[c] += 1;
               if(mp[c] >= 1) cnt -= 1;
               left++;
           }
           right++;
       }
       return res;
    }
}