滑动窗口解题模板

滑动窗口适用于固定长度的窗口问题，或者需要动态维护一个窗口的场景。

模板

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. 实现代码

• 根据模板实现滑动窗口

示例问题

原文地址：https://blog.csdn.net/weixin_43688870/article/details/145310698

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！