slide_window.md

滑动窗口

模板

/* 滑动窗口算法框架 */voidslidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/printf("window: [%d, %d)\n", left, right);
/********************/// 判断左侧窗口是否要收缩while (window needs shrink) {
// d 是将移出窗口的字符char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}

需要变化的地方

• 1、右指针右移之后窗口数据更新
• 2、判断窗口是否要收缩
• 3、左指针右移之后窗口数据更新
• 4、根据题意计算结果

示例

minimum-window-substring

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串

funcminWindow(sstring, tstring) string {
// 保存滑动窗口字符集win:=make(map[byte]int)
// 保存需要的字符集need:=make(map[byte]int)
fori:=0; i<len(t); i++ {
need[t[i]]++
}
// 窗口left:=0right:=0// match匹配次数match:=0start:=0end:=0min:=math.MaxInt64varcbyteforright<len(s) {
c=s[right]
right++// 在需要的字符集里面，添加到窗口字符集里面ifneed[c] !=0 {
win[c]++// 如果当前字符的数量匹配需要的字符的数量，则match值+1ifwin[c] ==need[c] {
match++
}
}
// 当所有字符数量都匹配之后，开始缩紧窗口formatch==len(need) {
// 获取结果ifright-left<min {
min=right-leftstart=leftend=right
}
c=s[left]
left++// 左指针指向不在需要字符集则直接跳过ifneed[c] !=0 {
// 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一// 因为win里面的字符数可能比较多，如有10个A，但需要的字符数量可能为3// 所以在压死骆驼的最后一根稻草时，match才减一，这时候才跳出循环ifwin[c] ==need[c] {
match--
}
win[c]--
}
}
}
ifmin==math.MaxInt64 {
return""
}
returns[start:end]
}

permutation-in-string

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 **s1 **的排列。

funccheckInclusion(s1string, s2string) bool {
win:=make(map[byte]int)
need:=make(map[byte]int)
fori:=0; i<len(s1); i++ {
need[s1[i]]++
}
left:=0right:=0match:=0forright<len(s2) {
c:=s2[right]
right++ifneed[c] !=0 {
win[c]++ifwin[c] ==need[c] {
match++
}
}
// 当窗口长度大于字符串长度，缩紧窗口forright-left>=len(s1) {
// 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件ifmatch==len(need) {
returntrue
}
d:=s2[left]
left++ifneed[d] !=0 {
ifwin[d] ==need[d] {
match--
}
win[d]--
}
}
}
returnfalse
}

find-all-anagrams-in-a-string

给定一个字符串 **s **和一个非空字符串 p，找到 **s **中所有是 **p **的字母异位词的子串，返回这些子串的起始索引。

funcfindAnagrams(sstring, pstring) []int {
win:=make(map[byte]int)
need:=make(map[byte]int)
fori:=0; i<len(p); i++ {
need[p[i]]++
}
left:=0right:=0match:=0ans:=make([]int,0)
forright<len(s) {
c:=s[right]
right++ifneed[c] !=0 {
win[c]++ifwin[c] ==need[c] {
match++
}
}
// 当窗口长度大于字符串长度，缩紧窗口forright-left>=len(p) {
// 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件ifright-left==len(p)&&match==len(need) {
ans=append(ans,left)
}
d:=s[left]
left++ifneed[d] !=0 {
ifwin[d] ==need[d] {
match--
}
win[d]--
}
}
}
returnans
}

longest-substring-without-repeating-characters

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

funclengthOfLongestSubstring(sstring) int {
// 滑动窗口核心点：1、右指针右移 2、根据题意收缩窗口 3、左指针右移更新窗口 4、根据题意计算结果iflen(s)==0{
return0
}
win:=make(map[byte]int)
left:=0right:=0ans:=1forright<len(s){
c:=s[right]
right++win[c]++// 缩小窗口forwin[c]>1{
d:=s[left]
left++win[d]--
}
// 计算结果ans=max(right-left,ans)
}
returnans
}
funcmax(a,bint)int{
ifa>b{
returna
}
returnb
}

总结

• 和双指针题目类似，更像双指针的升级版，滑动窗口核心点是维护一个窗口集，根据窗口集来进行处理
• 核心步骤
  • right 右移
  • 收缩
  • left 右移
  • 求结果

练习

• minimum-window-substring
• permutation-in-string
• find-all-anagrams-in-a-string
• longest-substring-without-repeating-characters