滑动窗口

查找与遍历

说明

维护连续区间并增量更新状态；下例求长度为 k 的最大区间和，时间 O(n)。

分析

先计算第一个固定长度窗口的和，随后每右移一步只减去离开的元素并加上新进入的元素。这样避免重复求和，使整体复杂度降为 O(n)。

长度2窗口在[2,1,5,3]上产生和3、6、8，每次减去离开值、加上进入值。固定长度求和允许负数；最大值必须从第一个合法窗口初始化，不能用0，否则全负数时出错。

查看图表代码

适用前提与边界

可变长度窗口需要明确扩张与收缩条件；这个示例只处理固定 k。 固定窗口不要求数组有序，允许负值；示例对非法k返回0，这与合法窗口最大和为0无法区分，正式接口应明确错误约定。

示例输入与调用

fmt.Println(MaxWindowSum([]int{2, 1, 5, 3}, 2))

运行输出

8

完整 Go 示例

package main

import "fmt"

func MaxWindowSum(a []int, k int) int {
	if k <= 0 || k > len(a) {
		return 0
	}
	s := 0
	for _, x := range a[:k] {
		s += x
	}
	best := s
	for i := k; i < len(a); i++ {
		s += a[i] - a[i-k]
		if s > best {
			best = s
		}
	}
	return best
}

func main() {
	fmt.Println(MaxWindowSum([]int{2, 1, 5, 3}, 2))
}