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