滑动窗口解题模板
滑动窗口适用于固定长度的窗口问题，或者需要动态维护一个窗口的场景。
模板
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. 实现代码
- 根据模板实现滑动窗口