76. 最小覆盖子串

2025/9/18 10:59:14 来源：https://blog.csdn.net/s773364/article/details/146923594 浏览: 次关键词：76. 最小覆盖子串

leetcode Hot 100系列

文章目录

一、核心操作
二、外层配合操作
三、核心模式代码
总结

一、核心操作

判断是否包含函数
先计算出t的哈希表，再通过滑动窗口遍历s，每次遍历s的元素都将其加入s的哈希表中，只要s的哈希表包含了t的哈希表，则移动左端，如果right-left小于ansRight-ansLeft则更新
最终如果ansLeft为负数，则返回“”，否则取ansRight和ansLeft的子串

提示：小白个人理解，如有错误敬请谅解！

二、外层配合操作

哈希表为128位数组

三、核心模式代码

代码如下：

class Solution {
public:bool is_covered(std::vector<int>& s_cnt, std::vector<int>& t_cnt){for(int i='A';i<='Z';i++){if(s_cnt[i]<t_cnt[i])return false;}for(int i='a';i<='z';i++){if(s_cnt[i]<t_cnt[i])return false;}return true;}std::string minWindow(std::string s, std::string t) {std::string res;int m=s.size();int n=t.size();std::vector<int> s_cnt(128,0);std::vector<int> t_cnt(128,0);if(m<n)return "";int ansLeft=-1,ansRight=m;int right=0;int left=0;for(int i=0;i<n;i++)t_cnt[t[i]]++;for(;right<m;right++){   s_cnt[s[right]]++;while(is_covered(s_cnt,t_cnt)){if((right-left)<(ansRight-ansLeft)){ansLeft=left;ansRight=right;}s_cnt[s[left++]]--;}}if(ansLeft<0)return "";return s.substr(ansLeft,ansRight-ansLeft+1);}
};