滑动窗口(Sliding window)

一、滑动窗口简介

类似于窗口的移动方式，窗口内部的多数元素保持稳定。滑动窗口技术的实际应用包括：网络流量控制以及令牌桶算法的实现。

二、滑动窗口特点

针对涉及数组或字符串中子元素的处理问题，以及寻找符合特定条件的连续区间的问题，例如“请确定满足xx条件的最x区间（子串、子数组）的相关属性”。

通过将原本嵌套结构的循环操作转化为单一循环形式，当区间发生变动时，可借助先前计算所得的结果对搜索范围进行有效裁剪，进而避免冗余运算，实现时间复杂度的优化。

三、示例题目

3.1 固定长度窗口

对于一个整数序列，需要求出所有长度为k的连续子序列中总和最大的那个。

暴力求解方式：

• 依次计算每个起始位置开始的k个元素之和，并记录最大值，该方法的时间复杂度为O(n*k)

优化策略：

• 设定一个长度为k的滑动窗口，该窗口在数组中从左至右逐步移动
• 在每次滑动过程中，通过减去左侧移出窗口的元素值，并加上右侧新进入窗口的元素值来实现快速求和
• 此方法有效避免了重复计算，从而提升了运算效率

    public int maxSum(int[] arr, int k) {
    	int n = arr.length;
    	if (n < k) return -1;
    	int maxSum = 0