滑动窗口
模板
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++ // 进行窗口内数据的一系列更新 ... } } }
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 }