做淘宝客网站好搭建吗?最新黑帽seo教程

76. 最小覆盖子串s

初始化和特判

//本题做题思想
//从头开始，首先找到一个包含所有字母的字串，将i移动到包含字串字母的位置，然后更新长度和字符串ans后，
//i的位置加1，j的位置也加1，从新开始上面的流程，找一个包含所有字符串t字母的子串unordered_map<char,int>need;//need记录下来每个字母‘需要’多少，为正数//对于不需要的字母和本来需要但超出数量的字母，依旧记录，但减1后变负数int cnt = 0;//cnt记录总共需要多少个int ansnum = 100010;//ans记录最短的字符子串，ansnum维护最小的长度string ans = "";if(s.size() < t.size() ) return ans;if(s == t) return s;

统计字符数

for(int i = 0; i < t.size();i++){need[t[i]]++;
}
cnt = t.size();

找满足题目条件的字符子串

int i = 0, j = 0;while(i < s.size()){while(j < s.size() && cnt > 0){if(need[s[j]] > 0) cnt--;need[s[j]]--;if(cnt == 0 || j == s.size() - 1)break;j++;//while循环记得递增}if(cnt != 0) return ans;while(i < j){if(need[s[i]] == 0) break;need[s[i]]++;i++;//while循环记得递增}if(j - i  + 1 < ansnum){ans = s.substr(i, j - i + 1);ansnum = j - i + 1;}cnt += 1;need[s[i]]++;i++,j++;//记得递增}

具体解析过程可看此题解，本题解为C++实现，链接题解为python