每日一题day1（Leetcode 76最小覆盖子串）

1.题目解析1.该题“讲人话”就是在一个字符串s中找到一个最短的能够涵盖子串所有字符的子串2.解法解法1暴力枚举hash表classSolution{public:stringminWindow(string s,string t){intms.size();intnt.size();if(mn)return;// 解决实例3的特殊情况unordered_mapchar,intneed;// 统计t中的字符需要的次数for(autoc:t){need[c];}intrequiredneed.size();// 记录字符种类intlenINT_MAX;intstart0;// 记录子串开始位置为后续返回字符串奠定基础for(inti0;im;i){intmatched0;unordered_mapchar,intwindow;for(intji;jm;j){charcs[j];if(need.count(c)){// 筛除不必要的元素window[c];// 记录子串中字符出现次数if(window[c]need[c])matched;// 达到目标}if(matchedrequired){intcurrentlenj-i1;if(currentlenlen){lencurrentlen;starti;// 更新位置}break;}}}returnlenINT_MAX?:s.substr(start,len);}};虽然这种解题方法容易想但是作为一道困难题是绝对不可能让你暴力O(n^2)过的这个时候我们就需要在暴力的基础上进行优化我们此处可以选择使用滑动窗口的方式对该问题进行优化解法2滑动窗口手动hashclassSolution{public:stringminWindow(string s,string t){inthash1[128]{0};// 统计t内字符出现的次数intkinds0;//统计有效字符个数for(autoch:t){if(hash1[ch]0)kinds;}inthash2[128]{0};intminlenINT_MAX,begin-1;for(intleft0,right0,count0;rights.size();right){charins[right];if(hash2[in]hash1[in])//进窗口加维护countcount;while(countkinds){//判断if(right-left1minlen){//更新结果minlenright-left1;beginleft;}charouts[left];//出·窗口维护countif(hash2[out]--hash1[out])count--;}}if(begin-1)return;elsereturns.substr(begin,minlen);}};