可以直接观看的网站正能量,做海报兼职网站,线上it培训机构,网站开发在线课程原题#xff1a;76. 最小覆盖子串 - 力扣#xff08;LeetCode#xff09; 题目解析#xff1a; 此题在这道题的基础上进行理解会更简单
leetcode --- 30. 串联所有单词的子串[C 滑动窗口/双指针]-CSDN博客 本题要求在s字符串中找到含有t字符串所有字符的最短子串。 也就是… 原题76. 最小覆盖子串 - 力扣LeetCode 题目解析 此题在这道题的基础上进行理解会更简单
leetcode --- 30. 串联所有单词的子串[C 滑动窗口/双指针]-CSDN博客 本题要求在s字符串中找到含有t字符串所有字符的最短子串。 也就是说s字符串中的字符可能有非t字符串中的字符或者多个t字符串中的字符即重复 那么和找异位词不同的是 不能简单地通过有效字符个数来判断找到符合要求的子串。所以我们用有效字符的种类来判断。 算法原理 滑动窗口哈希表 哈希表hash1用来统计t字符串中字符的频次再设置一个kinds变量当这个字符出现频次大于0时就表示有一个种类。 创建哈希表hash2统计窗口中的字符出现的频次创建count变量表示窗口中字符的种类 滑动窗口四步走 1.进窗口 在哈希表中更新right指针指向的元素的频次 check判断 hash2中这个字符的频次是否和hash1中的频次 相等 只有相等的时候才让count表示有效字符种类增加 2.判断即找到出窗口的前置条件 如果count 等于 kinds表示此时有效字符种类相等 3.更新状态 在进入滑动窗口之前先设置好两个变量begin 和 min_len分别用来记录符合要求的字符串的起始位置和长度 min_len与 right-left 1 比较 如果right-left 1更短则 min_len替换成更短的长度 将left赋值给begin 4.出窗口 check判断hash2中的出窗口字符频次是否等于hash1中的频次如果相等则有效字符种类 count-- 然后让left向右移动一位 最后返回结果时如果begin还等于初始值表示不存在最小覆盖子串返回空串 反之返回从begin开始长度为min_len的子字符串 代码编写
class Solution {
public:string minWindow(string s, string t) {int hash1[128] {0}; //保存t字符串中字符出现频次int kinds 0; //统计有效字符的种类for(auto ch : t){if( hash1[ch] 0){kinds;}}int hash2[128] {0};//统计窗口中字符出现频次int min_len INT_MAX,begin -1;for(int left 0,right 0,count 0; right s.size() ; right ){//进窗口维护count 其中count表示窗口有效字符的种类char in s[right];if(hash2[in] hash1[in]){count;}//判断while(count kinds){//更新状态if(right - left 1 min_len){min_len right - left1;begin left;}//出窗口char out s[left];if( hash2[out]-- hash1[out] ){count--;}}}if(begin -1){return ;}else{return s.substr(begin,min_len);}}
};
