最小覆蓋子串
給你一個(gè)字符串 S、一個(gè)字符串 T，請(qǐng)?jiān)谧址?S 里面找出：包含 T 所有字符的最小子串。
示例：
輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"
說明：
如果 S 中不存這樣的子串，則返回空字符串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-window-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

此題最大的收獲應(yīng)該是使用一個(gè)freq變量記錄字符數(shù)組中每個(gè)字符出現(xiàn)的次數(shù)。
如果是字符數(shù)組，也可以使用定義的int型數(shù)組，編譯器會(huì)根據(jù)字符的ASCII碼將字符轉(zhuǎn)換成int類型。

本題目也是一個(gè)經(jīng)典的滑動(dòng)窗口題目:
首先右邊界不斷擴(kuò)展，去尋找匹配字符;
設(shè)置一個(gè)變量match，根據(jù)frequncy去統(tǒng)計(jì)s中和t匹配的字符個(gè)數(shù);
當(dāng)滿足match已經(jīng)可以等于t的串長(zhǎng)時(shí)，可以收縮左邊界

class Solution {

    public String minWindow(String s, String t) {
    if(s==null||t==null||s.length()==0||t.length()==0) return "";
      int[] freq = new int[200];
      //使用frequency 記錄一個(gè)字符出現(xiàn)的次數(shù)
      int left=0;
      int right=0;
      //substring初始為""
      int start=0;
      int end=0;
      int match=0;//匹配的字符個(gè)數(shù)
      int minlength = s.length()+1;
      for (char c: t.toCharArray()){
          freq[c]++;
      }
      while(right<s.length()){//right max = s.length-1{
          char charRight = s.charAt(right);
          freq[charRight]--;//表示對(duì)于t中已經(jīng)匹配的字符，對(duì)應(yīng)的frequency減少
          //如果freq不為負(fù)數(shù)，則說明s中的某個(gè)字符也出現(xiàn)在t中
          if(freq[charRight]>=0){
            //匹配 match++
          match++;
          }       
          //為了保證substring包含右邊界
          right++;

 //什么時(shí)候可以移動(dòng)：如果存在已經(jīng)匹配的子串時(shí)可以移動(dòng)
 //條件就是 match==t.length()
       while(match==t.length()){

    //當(dāng)匹配長(zhǎng)度等于t.length，記錄此時(shí)的start和end，可以對(duì)左邊界收縮
         //后續(xù)循環(huán)繼續(xù)根據(jù)match更新start和end
         int size =right-left;
           if(size<minlength){
             minlength=size;
             start=left;
             end=right;
           }

       //如果移出了與t中可以匹配的字符         
         char charLeft = s.charAt(left);
     //不在t中的,freq一直是0
         freq[charLeft]++;    
        if(freq[charLeft]>0) //說明移出了已經(jīng)可以匹配的字符
        match--;
        left++; 
        }
      }
      return s.substring(start,end);
}
}