本文主要是介绍leetcode 76:最小覆盖子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题我使用了很笨的方式花了好久解决了，但是时间复杂度太度，只看网上查看源码，不得不说网上的答案基本都是一样的，但是对于基础相对薄弱的我来说这些代码看起来很是费劲，还用要加强C++基础的练习才行。
思路相对来说不是很难：
1 首先构架t字符串的hash表，因为字符与ASCII码较好的关系，使用vector数组map来构造hash表，所存的int型表示该字符出现的次数
vector<int> map(128,0); for(auto c: t)map[c]++;
2使用counter表示字符串t的个数，begin end表示子字符串的开始下标和结束下标，初始为0 d表示最短子字符串的个数 初始为最大值，head表示最小的子字符串的初始下标，初始为0 使用head和d可以找到子字符串
3首先，先将所有的t的字符串找到，每找到一个，count--，将当前子字符串的所有的int值减1，第一次找到t中所有的字符后，count=0，所有t中字符对应的hash值都等于0，而s在中不在t中的字符对应的hash值都小于0
4 当begin下标对应的字符等于0时，表示该字符在t中，往后移动窗口时，当前begin在窗口外，所以此时count++，begin向后移动之后，再次使得count==0，以此循环，直到窗口到达最后，找到最小的窗口
string minWindow(string s, string t) {vector<int> map(128,0);for(auto c: t)map[c]++;int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;while(end<s.size()){if(map[s[end]]>0){map[s[end]]-=1;end+=1;counter--; //in t}else{map[s[end]]-=1;end+=1;}while(counter==0){ //validif(end-begin<d)d=end-(head=begin);if(map[s[begin]]==0){map[s[begin]]+=1;begin+=1;counter++; //make it invalid}else{map[s[begin]]+=1;begin+=1;}}}return d==INT_MAX? "":s.substr(head, d);
}网上源码有点儿复杂，看起来很蒙，我将其简单化
这篇关于leetcode 76:最小覆盖子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
