【LeetCode】76. 最小覆盖子串（滑动窗口）

简书内代码已上传GitHub：点击我 去GitHub查看代码

前一篇做了题 无重复字符的最长子串 ，于是就对滑动窗口来了兴趣，初写滑动窗口问题还是很容易出错，希望做完几题后能有改善吧~~

滑动窗口～图片来源网络

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

示例：

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

说明：

• 如果 S 中不存这样的子串，则返回空字符串 ""。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路：

• 题目中的T串可能有重复字符，所以可以新建一个数组保存其字母出现频率

• 不在T内的字符fre值 = 0， 在T内初始值 = 1，所以我们可以让S中字符进入窗口时：如果 fre >= 0 , fre--。这样可以区分是否是T中元素

• 同样的，出窗口时fre++。第二步区分了是否为所需T中元素，是的话cnt--，直到cnt == 0时，说明已经找到全覆盖子串。

• 下一步就是进行左值针右移操作，缩小窗口。

看完算法思想了再来看看算法框架：

算法框架：

char* Func(char* S, char* T){
    int l, r;
    l = 0;r = 0;
    while(r < Slen){
        s[r]进入窗口
        
        while(窗口满足){
            l++ 窗口收缩
            当前窗口大小于此前最小窗口比较，保存
        }
        r++;
    }
    返回子串
}

算法框架看起来这题似乎很简单，但是用C语言解决此题，我们需要解决以下几个问题：

• 元素进入窗口时的计数以及判定

• 窗口满足的条件

• 获取子串，C语言就需要自己写Concat函数了

结合思路，下面我们来看滑动窗口代码：

注意要结合思路看 主体

完整代码：

// 求最小窗口
int min(int x, int y, int *ml, int *mr, int l, int r){
    if(y < x){
        *ml = l; *mr = r;
        return y;
    }else{
        return x;
    }
}


char * minWindow(char * s, char * t){
    // 左右指针
    int l, r;
    l = 0; r = 0;
    // 字符串长度
    int len1, len2;
    len1 = strlen(s); len2 = strlen(t);
    // 存储字母出现频率
    int fre[128] = {0};
    for(int i = 0; i < len2; ++i){
        ++fre[t[i]];
    }
    // 存储T中元素需求量
    int cnt = len2;
    // 最小串
    int ml, mr, mw;
    ml = 0; mr = -1; mw = len1 * 2;
    //滑动窗口
    while(r < len1){
        // 进入窗口，fre - 1
        --fre[s[r]];
        // 注意T中元素不一定是所需的T中元素
        // 如果是所需的T中元素， fre仍然大于0， 需求量 - 1
        if(fre[s[r]] >= 0) --cnt;
        // 包含所有T中元素
        while(cnt == 0){
            // 保存最小子串相关信息
            mw = min(mw, r - l + 1 , &ml, &mr, l, r);
            // 左指针右移，fre + 1，且如果出窗口的是所需的T中元素，需求量 + 1
            if(++fre[s[l++]] > 0) ++cnt;
        }
        ++r;
    }
    
    // 子串
    char *result = (char*)malloc(sizeof(char) * (mw + 1));
    // 如果 S 中不存这样的子串，则返回空字符串 ""
    if(mw == len1 * 2) return "";
    // 截取
    for(int i = ml ; i <= mr + 1 ; ++i){
        result[i - ml] = s[i];
    }
    result[mw] = '\0';
    return result;
}

如果有看不懂的，私信我！！！
~_^^
每天进步一点，加油！

End

END