leetcode 76 最小覆盖子串

一、题目描述

二、解题思路

整体思路：

模拟寻找最小覆盖子集的过程，由于可借助同向双指针且可以做到指针不回退，所以可以用滑动窗口的思想来解决这个问题。

具体思路：

(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);}
};