本文主要是介绍Leetcode每日刷题之76.最小覆盖子串(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题目解析
本题的题目是给定两个字符串 s 和 t ，找出在 s 中的某个最小子串保证该子串中包含所以 t 中出现的字母即可，并且该结果是唯一答案，找不到结果就直接返回空串即可
2.算法原理
关于本题的核心思路就是"滑动窗口"，具体实现是：
1.首先给定两个指针left和right，使用count统计窗口内有效字符的种类，之所以不是有效字符的个数是因为在最小子串中只要完全包含t中的所以字母即可，不需要一一对应，然后使用kinds统计t中的字母种类个数
2.right指针不断向右移动以达到进窗口的目的，在进窗口之后判断进入的字母种类个数是否完全等于t中该字符种类个数，如果等于则count++即窗口内有效字母种类增加
3.当count == kinds即窗口内有效字母种类出现频次等于t中所有字母种类个数时更新最下字符串长度，然后执行出窗口操作
4.出窗口之前需要判断即将出窗口的字母在窗口内出现的频次是否完全等于t中该字母出现频次，如果等于则代表该字符出窗口会导致窗口内有效字母的种类频次减少，则count--
5.最后判断最小子串是否存在，存在则直接返回，反之返回空串
3.代码展示
class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 };//统计 t 中所有字母出现次数int kinds = 0;//统计 t 中字母种类int minlen = INT_MAX;int begin = -1;for(auto ch : t){if(hash1[ch]++ == 0){kinds++;}}int hash2[128] = { 0 };//统计窗口内每个字母出现频次for(int left = 0,right = 0,count = 0;right < s.size();right++){char in = s[right];//进窗口 + 维护if(++hash2[in] == hash1[in]){count++;}//判断出窗口while(count == kinds){if(minlen > right - left + 1){minlen = right - left + 1;begin = left;}//出窗口 + 维护 countchar out = s[left++];if(hash2[out]-- == hash1[out]){count--;}}}if(begin == -1){return "";}else{return s.substr(begin,minlen);}}
};
这篇关于Leetcode每日刷题之76.最小覆盖子串(C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
