[L1] 固定大小滑动窗口求子数组最大和

一句话结论

固定窗口先填满再整体平移，每步减去左端、加入右端，将 O(n²) 暴力降至 O(n)。

体系讲解

问题定义

给定整数数组 $nums 和窗口大小 $k，找出所有长度为 $k 的连续子数组中，元素之和最大的值。

暴力方案

对每个起点 i，重新累加 nums[i..i+k-1]——两层循环，时间 O(n·k)，当 k 较大时退化严重。

滑动窗口方案

关键洞察：相邻两个窗口有 k-1 个元素重叠，只有首尾各 1 个元素不同。

窗口 [i, i+k-1] → 窗口 [i+1, i+k]：
新窗口和 = 旧窗口和 - nums[i] + nums[i+k]

因此只需在第一个窗口建立初始和，此后每次平移 O(1) 更新。

执行流程

nums = [2, 1, 5, 1, 3, 2], k = 3

阶段 1 — 填满第一个窗口（i = 0..k-1）：
  windowSum = 2 + 1 + 5 = 8, maxSum = 8

阶段 2 — 滑动（i = k..n-1）：
  i=3: windowSum = 8 - nums[0] + nums[3] = 8 - 2 + 1 = 7, maxSum = 8
  i=4: windowSum = 7 - nums[1] + nums[4] = 7 - 1 + 3 = 9, maxSum = 9
  i=5: windowSum = 9 - nums[2] + nums[5] = 9 - 5 + 2 = 6, maxSum = 9

结果: 9（子数组 [5, 1, 3]）

时间/空间复杂度

方案	时间	空间
暴力双循环	O(n·k)	O(1)
固定滑动窗口	O(n)	O(1)

固定窗口 vs 变长窗口

固定滑动窗口的窗口大小 k 在整个过程中不变，只做整体平移。
变长滑动窗口（L2 主题）的窗口大小根据条件动态伸缩，需要额外的缩窗逻辑。

考察意图

考查候选人是否掌握"利用重叠子结构避免重复计算"的思想——这是动态规划和滑动窗口的共同根基。固定窗口是所有滑动窗口题目的入门，能否快速写出不越界的模板是关键评估点。

追问链

1. 如果 k > 数组长度会怎样？
   简答：无法构成任何长度为 k 的窗口，应直接返回 0 或抛出异常，并在代码入口做边界检查 if ($k > count($nums)) return 0。

2. 固定窗口的起始条件为何是"先填满再滑动"？能否边填边判断？
   简答：可以，但逻辑会更复杂（需在每一步判断窗口是否已满）。先填满再滑动将"建立初始状态"与"更新状态"分离，代码更清晰，边界条件更少，是推荐写法。

3. 这道题和前缀和有什么关系？
   简答：sum(i..j) = prefix[j+1] - prefix[i]，前缀和也能 O(1) 求任意子数组和，但需要 O(n) 额外空间。滑动窗口只需 O(1) 空间，但只适用于"窗口连续平移"的场景；前缀和更通用，可回答任意区间查询。

4. 如何扩展为"找最大和的窗口起始下标"？
   简答：记录 maxSum 更新时的起始下标 $start = $i - $k + 1，最终返回 [$start, $start + $k - 1] 即为最大和窗口的区间。

易错点

1. 滑动时左端下标算错：平移到 i 时移出的是 nums[i - k]，而非 nums[i - 1]。将减去的下标写成 $i - 1 是最常见的越界/计算错误。
2. 循环范围少一：滑动阶段循环 for ($i = $k; $i < $n; $i++)，写成 $i <= $n - 1 等价，但写成 $i < $n - 1 会漏掉最后一个窗口。
3. 整数溢出（PHP 通常不需担心）：PHP 中整数自动升为 float，但面试中若题目注明数字范围极大，需说明语言特性；其他语言（Java/C++）需显式用 long。

代码示例

<?php

function maxSumSubarray(array $nums, int $k): int
{
    $n = count($nums);
    if ($k > $n) return 0;

    // 阶段 1：建立第一个窗口
    $windowSum = array_sum(array_slice($nums, 0, $k));
    $maxSum    = $windowSum;

    // 阶段 2：滑动窗口
    for ($i = $k; $i < $n; $i++) {
        $windowSum += $nums[$i] - $nums[$i - $k];
        $maxSum = max($maxSum, $windowSum);
    }

    return $maxSum;
}

// 演示
var_dump(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // int(9)
var_dump(maxSumSubarray([1, 2, 3, 4, 5],    2)); // int(9)