esc to dismiss

滑动窗口

滑动窗口使用两个指针来完成滑动。

设定两个游标指针,一个指窗口左侧(start),一个指向窗口右侧(end),起始时都指向0,右侧指针(end)先向右滑动,左侧指针(start)再向右滑动,保持窗口内的值符合条件。

一个典型的滑动窗口解法代码如下:(1004题为例)

func longestOnes(nums []int, k int) int {
    start, end := 0, 0
    length := 0
    size := len(nums)
    remain := k

    for start < size {
        if end < start {
            end = start
        }

        for end < size && (nums[end] == 1 || remain > 0) {
            if nums[end] == 0 {
                remain--
            }
            length = max(length, end - start + 1)
            end++
        }

        if nums[start] == 0 && end > start {
            remain++
        }
        start++
    }

    return length
}

start 和 end 代表左右两个游标指针,两层嵌套的 for 循环,外层左指针右滑,内层右指针右滑。最核心的逻辑如下所示:

for start < size {
    for end < size && 条件判断使得窗口满足限定条件 {
    逻辑处理...(收集满足条件的数据)
      end++
    }
    start++
}

需要注意的是,有些看似滑动窗口的题其实不是,如 560. 和为K的子数组 这其实是一个 前缀和 的题.

x