Skip to content

slide_window.md

Latest commit

History

History
217 lines (168 loc) · 6.59 KB

slide_window.md

File metadata and controls

217 lines (168 loc) · 6.59 KB
Raw

滑动窗口

模板

/* 滑动窗口算法框架 */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 所有字母的最小子串

classSolution:
defminWindow(self, s: str, t: str) ->str:
target=collections.defaultdict(int)
window=collections.defaultdict(int)
forcint:
target[c] +=1min_size=len(s) +1min_str=''l, r, count, num_char=0, 0, 0, len(target)
whiler<len(s):
c=s[r]
r+=1ifcintarget:
window[c] +=1ifwindow[c] ==target[c]:
count+=1ifcount==num_char:
whilel<randcount==num_char:
c=s[l]
l+=1ifcintarget:
window[c] -=1ifwindow[c] ==target[c] -1:
count-=1ifmin_size>r-l+1:
min_size=r-l+1min_str=s[l-1:r]
returnmin_str

permutation-in-string

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

classSolution:
defcheckInclusion(self, s1: str, s2: str) ->bool:
target=collections.defaultdict(int)
forcins1:
target[c] +=1r, num_char=0, len(target)
whiler<len(s2):
ifs2[r] intarget:
l, count=r, 0window=collections.defaultdict(int)
whiler<len(s2):
c=s2[r]
ifcnotintarget:
breakwindow[c] +=1ifwindow[c] ==target[c]:
count+=1ifcount==num_char:
returnTruewhilewindow[c] >target[c]:
window[s2[l]] -=1ifwindow[s2[l]] ==target[s2[l]] -1:
count-=1l+=1r+=1else:
r+=1returnFalse

find-all-anagrams-in-a-string

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

classSolution:
deffindAnagrams(self, s: str, p: str) ->List[int]:
target=collections.defaultdict(int)
forcinp:
target[c] +=1r, num_char=0, len(target)
results= []
whiler<len(s):
ifs[r] intarget:
l, count=r, 0window=collections.defaultdict(int)
whiler<len(s):
c=s[r]
ifcnotintarget:
breakwindow[c] +=1ifwindow[c] ==target[c]:
count+=1ifcount==num_char:
results.append(l)
window[s[l]] -=1count-=1l+=1whilewindow[c] >target[c]:
window[s[l]] -=1ifwindow[s[l]] ==target[s[l]] -1:
count-=1l+=1r+=1else:
r+=1returnresults

longest-substring-without-repeating-characters

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

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

classSolution:
deflengthOfLongestSubstring(self, s: str) ->int:
last_idx= {}
l, max_length=0, 0forr, cinenumerate(s):
ifcinlast_idxandlast_idx[c] >=l:
max_length=max(max_length, r-l)
l=last_idx[c] +1last_idx[c] =rreturnmax(max_length, len(s) -l) # note that the last substring is not judged in the loop

总结

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

练习