滑动窗口 最小覆盖子串

基本模板

定义状态向右增大窗口向左缩小窗口持续迭代 void window(string s, string t) { unordered_map<char, int> window, target; for (char c : t) { ++target[c]; } int left = 0, right = 0; // 初始化双指针 ... // 定义状态值 while (right < s.size()) { // 增大窗口 char c = s[righ] ++right; ... // 更新window while (达到缩小窗口的条件) { ... // 更新状态值 char c = s[left]; ++left; ... // 更新window/状态值 } } }

应用场景

最小覆盖子串（LeetCode76）字符串排列（LeetCode567）统计字母异位词（LeetCode438）最长无重复子串（LeetCode3）

最小覆盖子串

给出两个字符串 和 ，要求在的时间复杂度内在 中找出最短的包含 中所有字符的子串。 例如： S =“XDOYEZODEYXNZ” T =“XYZ” 找出的最短子串为"YXNZ".

注意： 如果 中没有包含 中所有字符的子串，返回空字符串 “”； 满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

哈希+指针

以哈希为主，不断收集迭代比较，取最优

func minWindow( S string , T string ) string { tm := make(map[byte]int,0) for i:=0;i<len(T);i++{ tm[T[i]]++ } minStr :="" ssm := make(map[byte]int,0) for i,k:=0,-1;i<len(S);i++{ if _,ok:=tm[S[i]];ok { if k ==-1 { k = i } ssm[S[i]]++ } if k != -1 && cmpMap(tm,ssm){ if k >len(S)-len(T){ break } cur :=S[k:i+1] if len(minStr)>len(cur) || len(minStr)==0 { minStr = cur } i=k k=-1 ssm = make(map[byte]int,0) } } return minStr } func cmpMap(t, s map[byte]int)bool { if len(t) != len(s){ return false } for k,v :=range s { if v < t[k] { return false } } return true }

滑动窗口

用两个字典分别维护窗口中字符的统计数量、以及被求解子串中字符的统计数量用双指针遍历主字符串，双指针的初始值均为0，窗口的范围是[left, right)（左闭右开）遍历过程中，不断增大、缩小窗口，并更新状态 import "math" func minWindow( S string , T string ) string { var start int sm := map[byte]int{} minLen := math.MaxInt16 mt := make(map[byte]int, 0) for i,_ := range T { mt[T[i]]++ } for left,right,vaild:=0,0,0;right<len(S);{ rc := S[right] right++ if cnt,ok := mt[rc];ok{ sm[rc]++ if sm[rc] == cnt { vaild++ } } for vaild == len(mt){ if right - left < minLen { minLen = right-left start = left } lc := S[left] left++ if cnt,ok := mt[lc];ok { if sm[lc] == cnt { vaild-- } sm[lc]-- } } } if minLen == math.MaxInt16 { return "" } return S[start:start+minLen] }