算法刷题系列（十七）：滑动窗口——维护满足条件的连续区间

算法刷题系列（十七）：滑动窗口——维护满足条件的连续区间

前缀和为区间查询提供了随机访问方式；滑动窗口则适合连续区间的在线扫描。左右端点之间构成窗口，右端点扩展窗口，左端点在条件不满足时收缩窗口。

窗口看起来只是两根指针，真正决定算法是否正确的是条件的单调性。本篇用非负数组中“和不超过上限的最长连续区间”作为例子，并说明为什么有负数时相同的收缩逻辑不一定成立。

一、题目与条件

给定非负整数数组 values 和上限 limit，找出总和不超过 limit 的最长连续子数组长度。

例子：

values = [2, 1, 3, 2, 1], limit = 5

较长的候选区间 [2, 1, 3] 总和为 6，超过上限。实际最长合法长度为 2，例如 [2, 1] 或总和为 5 的 [3, 2]。

二、窗口不变量和指针移动

维护半开窗口 [left, right) 以及窗口内元素和 windowSum。每次把 values[right] 加入窗口：

1. right 向右扩展一格；
2. 当 windowSum > limit 时，从左侧移除元素并增加 left；
3. 此时窗口重新满足总和不超过上限；
4. 用当前窗口长度更新答案。

为什么非负是关键？右端加入非负数只会让窗口和不减；左端移除非负数只会让窗口和不增。因此超过上限后，收缩左端能够修复条件，而且被收缩掉的起点不可能在未来重新变成更优的可行窗口。

三、手动推演

values = [2, 1, 3, 2, 1], limit = 5

加入值	窗口和	处理后窗口	长度	最长
2	2	[2]	1	1
1	3	[2, 1]	2	2
3	6	移除 2 后为 4，窗口 [1, 3]	2	2
2	6	移除 1 后为 5，窗口 [3, 2]	2	2
1	6	移除 3 后为 3，窗口 [2, 1]	2	2

答案是 2。

四、Java 实现

public class SlidingWindow {
    public static int longestSumAtMost(int[] values, long limit) {
        if (values == null) {
            throw new IllegalArgumentException("values must not be null");
        }
        for (int value : values) {
            if (value < 0) {
                throw new IllegalArgumentException(
                    "values must contain only non-negative numbers"
                );
            }
        }
        if (limit < 0) {
            return 0;
        }

        int left = 0;
        int best = 0;
        long windowSum = 0;
        for (int right = 0; right < values.length; right++) {
            windowSum += values[right];
            while (windowSum > limit) {
                windowSum -= values[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

空数组返回 0。limit < 0 时，非负元素的任何非空区间都不可能合法，因此也返回 0。

五、Python 实现

def longest_sum_at_most(values: list[int], limit: int) -> int:
    if values is None:
        raise ValueError("values must not be None")
    if any(value < 0 for value in values):
        raise ValueError("values must contain only non-negative numbers")
    if limit < 0:
        return 0

    left = 0
    best = 0
    window_sum = 0
    for right, value in enumerate(values):
        window_sum += value
        while window_sum > limit:
            window_sum -= values[left]
            left += 1
        best = max(best, right - left + 1)
    return best

assert longest_sum_at_most([2, 1, 3, 2, 1], 5) == 2
assert longest_sum_at_most([], 5) == 0
assert longest_sum_at_most([0, 0, 0], 0) == 3
assert longest_sum_at_most([8], 5) == 0

六、复杂度与负数反例

每个元素最多进入窗口一次、离开窗口一次，所以时间复杂度为 O(n)，额外空间为 O(1)。

若允许负数，滑动窗口的单调性就可能失效。例如 [5, -4, 5]，上限为 6。右端刚加入第一个 5 后符合条件；若算法依据另一个条件提前丢弃左端，后面的 -4 会使窗口总和下降。此时被丢弃的起点可能重新有用，单调收缩的证明不成立。

对负数数组中的目标和问题，应考虑前缀和加哈希表等方法；若要求最长满足复杂条件的区间，则需要重新分析结构，不能直接套用窗口模板。

七、常见错误

1. 没证明扩展和收缩的单调性：双指针线性复杂度依赖窗口端点不回退。
2. 把任意整数数组都当作可用滑窗：负数会破坏很多基于和的单调性。
3. 条件不满足时用 if 而非 while：一个元素可能需要连续移除多个左端值。
4. 先更新答案再修复窗口：可能记录超限窗口。
5. 窗口长度边界写错：闭合索引的长度为 right - left + 1；半开窗口长度则是 right - left。
6. 忽略单个元素也超限：收缩循环允许把窗口缩成空区间。

八、与下一篇的连接

滑动窗口维护的是连续区间，并依靠左右端点移动更新状态。字符串也可以使用相向指针或窗口，但回文判断更直接地利用对称性：从区间两端向中心比较。下一篇将从简单回文判断扩展到最长回文子串。

小结

滑动窗口不是“看到连续区间就套”的技巧。先定义窗口、状态和合法性，再证明扩展和收缩的单调性。对非负数组，窗口和超过上限时收缩左端可靠；元素可为负数时则要另找方法。