分析给定两个字符串s和t长度分别是m和n返回 s 中的最短窗口 子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。其实就是可以包含其他字母的最短异位词。题解滑动窗口计数我们可以沿用异位词的思想异位词438题窗口字符计数 t tt计数最小覆盖子串76题窗口字符计数≥ t \ge t≥t计数滑动窗口右指针不断扩大窗口一旦窗口[l, r]满足覆盖 t 全部字符就不断收缩左指针记录最小合法窗口。check()遍历字母判断当前窗口字符计数是否满足t的需求。代码// 判断窗口是否满足覆盖tboolcheck(constvectorintsCount,constvectorinttCount){for(inti0;i128;i){if(tCount[i]0sCount[i]tCount[i]){returnfalse;}}returntrue;}classSolution{public:stringminWindow(string s,string t){intsLens.size();inttLent.size();if(sLentLen)return;vectorintsCount(128,0);vectorinttCount(128,0);for(charch:t){tCount[ch];}intl0;intstart0;intminLenINT_MAX;for(intr0;rsLen;r){sCount[s[r]];while(check(sCount,tCount)){intcurr-l1;if(curminLen){minLencur;startl;}sCount[s[l]]--;l;}}if(minLenINT_MAX)return;returns.substr(start,minLen);}};时间复杂度O ( 128 ⋅ n ) O(128 \cdot n)O(128⋅n)n是s长度。外层 r 循环 n 次每一次进入while会调用check()循环 128 次左右指针总共最多移动2n次。128 是常数平均可以看作O ( n ) O(n)O(n)。空间复杂度O ( 1 ) O(1)O(1)固定大小 128 数组和输入规模无关。优化版滑动窗口维护 valid 变量记录满足数量要求的字符种类不需要每次遍历 128 数组。validt 中一共有多少种需要的字符match当前窗口里已经满足数量要求的字符种类当match valid窗口完全覆盖 t进入收缩阶段代码classSolution{public:stringminWindow(string s,string t){vectorintsCount(128,0),tCount(128,0);for(charc:t)tCount[c];intvalid0;//满足条件的字符种类for(inti0;i128;i){if(tCount[i]0)valid;}intl0,start0,minLenINT_MAX;intmatch0;//当前窗口匹配成功的种类for(intr0;rs.size();r){charcs[r];sCount[c];if(tCount[c]sCount[c]tCount[c]){match;}while(matchvalid){intcurr-l1;if(curminLen){minLencur;startl;}charouts[l];if(tCount[out]sCount[out]tCount[out]){match--;}sCount[out]--;l;}}returnminLenINT_MAX?:s.substr(start,minLen);}};时间复杂度O ( n m ) O(nm)O(nm)ns 长度mt 长度。左右指针各走一遍 s无内层循环。空间复杂度O ( 1 ) O(1)O(1)固定 128 大小数组常数空间。76. 最小覆盖子串 - 力扣LeetCode
分析给定两个字符串s和t长度分别是m和n返回 s 中的最短窗口 子串使得该子串包含t中的每一个字符包括重复字符。如果没有这样的子串返回空字符串。测试用例保证答案唯一。其实就是可以包含其他字母的最短异位词。题解滑动窗口计数我们可以沿用异位词的思想异位词438题窗口字符计数 t tt计数最小覆盖子串76题窗口字符计数≥ t \ge t≥t计数滑动窗口右指针不断扩大窗口一旦窗口[l, r]满足覆盖 t 全部字符就不断收缩左指针记录最小合法窗口。check()遍历字母判断当前窗口字符计数是否满足t的需求。代码// 判断窗口是否满足覆盖tboolcheck(constvectorintsCount,constvectorinttCount){for(inti0;i128;i){if(tCount[i]0sCount[i]tCount[i]){returnfalse;}}returntrue;}classSolution{public:stringminWindow(string s,string t){intsLens.size();inttLent.size();if(sLentLen)return;vectorintsCount(128,0);vectorinttCount(128,0);for(charch:t){tCount[ch];}intl0;intstart0;intminLenINT_MAX;for(intr0;rsLen;r){sCount[s[r]];while(check(sCount,tCount)){intcurr-l1;if(curminLen){minLencur;startl;}sCount[s[l]]--;l;}}if(minLenINT_MAX)return;returns.substr(start,minLen);}};时间复杂度O ( 128 ⋅ n ) O(128 \cdot n)O(128⋅n)n是s长度。外层 r 循环 n 次每一次进入while会调用check()循环 128 次左右指针总共最多移动2n次。128 是常数平均可以看作O ( n ) O(n)O(n)。空间复杂度O ( 1 ) O(1)O(1)固定大小 128 数组和输入规模无关。优化版滑动窗口维护 valid 变量记录满足数量要求的字符种类不需要每次遍历 128 数组。validt 中一共有多少种需要的字符match当前窗口里已经满足数量要求的字符种类当match valid窗口完全覆盖 t进入收缩阶段代码classSolution{public:stringminWindow(string s,string t){vectorintsCount(128,0),tCount(128,0);for(charc:t)tCount[c];intvalid0;//满足条件的字符种类for(inti0;i128;i){if(tCount[i]0)valid;}intl0,start0,minLenINT_MAX;intmatch0;//当前窗口匹配成功的种类for(intr0;rs.size();r){charcs[r];sCount[c];if(tCount[c]sCount[c]tCount[c]){match;}while(matchvalid){intcurr-l1;if(curminLen){minLencur;startl;}charouts[l];if(tCount[out]sCount[out]tCount[out]){match--;}sCount[out]--;l;}}returnminLenINT_MAX?:s.substr(start,minLen);}};时间复杂度O ( n m ) O(nm)O(nm)ns 长度mt 长度。左右指针各走一遍 s无内层循环。空间复杂度O ( 1 ) O(1)O(1)固定 128 大小数组常数空间。76. 最小覆盖子串 - 力扣LeetCode
