一、題目描述

二、解題思路

整體思路：

模擬尋找最小覆蓋子集的過程，由于可借助同向雙指針且可以做到指針不回退，所以可以用滑動窗口的思想來解決這個問題。

具體思路：

(1)數組hash1用于統計t中每一個字符出現的頻次，變量kinds用于統計有效字符的種類，例如t為“aabc”,則kinds為3；

(2)數組hash2用于統計窗口內每一個字符的頻次；

(3)滑動窗口要素：

<1>進窗口：進入hash1，進之后維護count

?//進窗口

?char in=s[right];

?if(hash1[in]==++hash2[in]) count++;

<2>判斷:窗口內的字符串為覆蓋子集

?while(count==kinds)

<3>更新：更新len和start

//更新

if(right-left+1<len){

? ? ? ? len=right-left+1;

? ? ? ? start=left;

}

<4>出窗口：出hash1，出之前維護count

//出窗口

char out=s[left++];

if(hash2[out]--==hash1[out]) count--;

(4)如果未找到合法的覆蓋子集，就返回空字符串。如果找到了最小覆蓋子串，就返回這個最小的覆蓋子串。

三、代碼實現

class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0};//統計t中每一個字符的頻次int kinds=0;//統計有效字符的種類for(auto c:t) if(hash1[c]++==0) kinds++;int hash2[128]={0};//統計窗口內每一個字符的頻次//滑動窗口int start,len=INT_MAX;for(int left=0,right=0,count=0;right<s.size();right++){//進窗口char in=s[right];if(hash1[in]==++hash2[in]) count++;//判斷while(count==kinds){//更新if(right-left+1<len){len=right-left+1;start=left;}//出窗口char out=s[left++];if(hash2[out]--==hash1[out]) count--;}}return len==INT_MAX?"":s.substr(start,len);}
};