Week 43 @ 2024 算法周记【滑动窗口】
- Bryan
滑动窗口
模板
int left = 0, right = 0;
while (right < nums.size()) {
// 增大窗口
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[left]);
left++;
}
}// 滑动窗口算法伪码框架
func slidingWindow(s string) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 如果我想记录窗口中的元素和，就可以只用一个 int
var window = ...
left, right := 0, 0 // 把索引左闭右开区间 [left, right) 称为一个「窗口」
for right < len(s) {
// c 是将移入窗口的字符
c := rune(s[right])
window[c]++
// 增大窗口
right++
// 进行窗口内数据的一系列更新
...
// *** debug 输出的位置 ***
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
fmt.Println("window: [",left,", ",right,")")
// ***********************
// 判断左侧窗口是否要收缩
for left < right && window needs shrink { //replace "window needs shrink" with actual condition
// d 是将移出窗口的字符
d := rune(s[left])
window[d]--
// 缩小窗口
left++
// 进行窗口内数据的一系列更新
...
}
}
}LC 76. Minimum Window Substring 最小覆盖子串
https://leetcode.com/problems/minimum-window-substring/
func minWindow(s string, t string) string {
T := toWindow(t)
initialResult := "x" + s
result := initialResult
var window [52]int
l, r := 0, 0
for r < len(s) {
windowAdd(&window, s[r])
r++
// fmt.Println("window: [",l,", ",r,")", s[l:r], "->", result)
for l < r && windowContains(window, T) {
if r - l < len(result) {
result = s[l:r]
}
windowRemove(&window, s[l])
l++
}
}
if result == initialResult {
return ""
}
return result
}
func toIndex(c byte) int {
if c >= 'A' && c <= 'Z' {
return int(c - 'A')
} else if c >= 'a' && c <= 'z' {
return 26 + int(c - 'a')
} else {
panic("Invalid character")
}
}
func toWindow(s string) (w [52]int) {
for _, r := range s {
w[toIndex(byte(r))]++
}
return
}
func windowAdd(window *[52]int, c byte) {
(*window)[toIndex(c)]++
}
func windowRemove(window *[52]int, c byte) {
(*window)[toIndex(c)]--
}
func windowContains(window1, window2 [52]int) bool { // window1 contains all window2
for i := range window1 {
if window1[i] < window2[i] {
return false
}
}
return true
}优化
优化点：
利用 valid + expectValid 优化 windowContains 的判断
原来的 windowContains 每次都要遍历 window 和 need，优化后不需要了
valid 是「need 中有的字符在 window 中也有至少相同数量的字符数」（即 s 已经满足了 t 要求的字符数）
通过操作 valid 可更好的利用窗口的特性，降低比较成本
利用 [start, end) 替换 result - 避免每次创建 string（虽然按照 Go 的实现应该成本不大，不一定很有效的优化，但至少是个差异点、至少降低了内存分配）
（其实不算个优化，是个备注而已）网上的答案大都用了 map，但我觉得既然已经限定了字符只能是 a-zA-z，所以用 array 应该比 map 要效率高
LC 567. Permutation in String 字符串的排列
https://leetcode.com/problems/permutation-in-string/
利用和上一题（LC.76）类似的优化，另一解法
还有另一种思路 —— 条件不是 valid，而是窗口定长
注意判断窗口定长的地方换成了 if —— 其实 for 也是可以的，但因为只会收缩一次窗口所以 if 也 OK —— 甚至可以判断成 if r - l == len(s1) 因为只会在窗口长度等于 len(s1) 时触发一次窗口收缩
LC 438. Find All Anagrams in a String 找到字符串中所有字母异位词
https://leetcode.com/problems/find-all-anagrams-in-a-string/
与上一题几乎一样 —— 只是将找到时返回改成了找到所有结果后一起返回
多解：一直在用 []int 代替 map，本题再搞个用 map 的解法
（虽然时间复杂度和用 [26]int 一样，但用 map 算是个负优化 —— 可以从 LC 的实际执行时间看出来，整整慢了十倍（1ms → 10ms））
LC 3. Longest Substring Without Repeating Characters 无重复字符的最长子串
https://leetcode.com/problems/longest-substring-without-repeating-characters/
注：
dup 存储重复值 —— 其实用不到，重复了直接收缩窗口就行（下面做优化）
window 因为有各种可能的值，因此没法用
[]int优化 —— 其实也有，因为题目限定在了 ASCII 以内 —— 为了简化，采用 map 但是初始化长度为 128
优化 - 不用 dup
进一步优化 - 不用 map
使用切片果然比 map 快！！从 8ms 直接降低到 0ms 。。