leetcode 76. Minimum Window Substring
2021-06-05 08:04
标签：http 一个 bsp span 时间复杂度 .com nim while 头部 https://www.cnblogs.com/grandyang/p/4340948.html O(n)的时间复杂度 滑动窗口 存储t中所有的字符和对应出现的次数。然后从s的头部开始滑动，遇到一个t中的字符就减一次，并且只要是次数大于0的情况，肯定是成功匹配了一个字符。直到所有成功匹配的字符个数等于t的个数，实际上也就是全都匹配了，再滑动最左边的位置。如果有一个字符的次数大于0了，说明现在滑动的位置已经缺字符了，又继续滑动右边的边界。 leetcode 76. Minimum Window Substring 标签：http 一个 bsp span 时间复杂度 .com nim while 头部 原文地址：https://www.cnblogs.com/ymjyqsx/p/10806836.htmlclass Solution {
public:
string minWindow(string s, string t) {
unordered_mapchar,int> m;
for(int i = 0;i )
m[t[i]]++;
string res = "";
int left = 0,count = 0,length = INT_MAX;
for(int i = 0;i ){
if(--m[s[i]] >= 0)
count++;
while(count == t.size()){
if(i - left + 1 length){
res = s.substr(left,i - left + 1);
length = i - left + 1;
}
if(++m[s[left]] > 0)
count--;
left++;
}
}
return res;
}
};
文章标题：leetcode 76. Minimum Window Substring
文章链接：http://soscw.com/essay/90785.html