滑动窗口解题模板
滑动窗口适用于固定长度的窗口问题，或者需要动态维护一个窗口的场景。
模板
public int slidingWindowTemplate(int[] nums, int k) {
int n = nums.length;
int maxSum = 0; // 记录最大值（或最小值）
int windowSum = 0; // 当前窗口的值
// 初始化窗口的值（前 k 个元素）
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
maxSum = windowSum;
// 滑动窗口：从第 k 个元素开始
for (int i = k; i < n; i++) {
// 窗口右移：加入新元素，移除旧元素
windowSum += nums[i] - nums[i - k];
// 更新最大值（或最小值）
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}适用场景
- 固定长度的窗口问题。
- 需要动态维护窗口内的值。
- 例如：
- 最大/最小子数组和。
- 最大/最小连续子区间的某些属性。
解题步骤总结
1. 理解题目
- 确定是否涉及连续子数组或子区间。
- 确定是否需要固定长度的窗口。
- 确定目标是最大化还是最小化某些值。
2. 选择技术
- 滑动窗口：固定长度的窗口问题。
- 前缀和：任意区间的快速查询问题。
3. 分解问题
- 找到基础部分（固定值）。
- 找到优化部分（需要动态维护或快速查询的值）。
4. 实现代码
- 根据模板实现滑动窗口