LeetCode76-最小覆盖子串：滑动窗口（Cpp+Golang）
题目链接：LeetCode76
题意
给定两个字符串s和t，求s中最小的子串，使得该子串包含t中所有的字符。
子串：字符串中连续的区间组成的字符串。
题解
- 求最小连续区间！滑动窗口！冲！
- 用一个map：mpt保存字符串t中的所有字符的出现情况
- 用一个map：mps保存当前窗口所有字符的出现情况
- 对于每一个窗口，用check函数判定其窗口可用性
- check函数，比较两个map的值，只有当mpt中的所有键对应值严格等于mps中所有键的对应值时候，才是一个合理有效的窗口。
- 虽然技术上确实是一个滑动窗口，但是验证check函数比较暴力，所有复杂度略高，Cpp实现过程中，需要使用unordered_map，不然会超时。
代码（Golang）
func minWindow(s string, t string) string { mps,mpt:=make(map[byte]int),make(map[byte]int) for i:=range t{ mpt[t[i]]++ } ansL,ll,l,r:=-1,math.MaxInt64,0,0 check:=func()bool{ for k,v:=range mpt{ if mps[k]<v{ return false } } return true } for ;r<len(s);r++{ if r0{ mps[s[r]]++ } for check()&& l<=r{ if r-l+10{ mps[s[l]]-- } l++ } } if ll==math.MaxInt64{ return "" } return s[ansL:ansL+ll]}代码（Cpp）
class Solution {public: #define len(s) s.size() unordered_mapmp,mpp; bool check(){ for(auto i:mp){ if(mpp[i.first]<i.second){ // cout<<i.first<<" "<<i.second<r;r++){ if(r0){ mpp[s[r]]++; } while(check()&&(l<=r)){ if(r-l+10){ mpp[s[l]]--; //cout<<l<<" "<<r<<" "<<s[l]<<endl; } l++; //cout<<l<<' '<<r<<endl; } } if (ansL==-1)return ""; //cout<<ansL<<' '<<len<<' '<<r; return s.substr(ansL,len); }};