连续子数组最小和：前缀和与滑动窗口解法详解

1. 题面拆解：从"心痛"故事到连续子数组最小和

1.1 题目真正在求什么

在洛谷刷题的时候，点开 P1614 这个题号，第一眼看见"爱与愁的心痛"这个名字，我还以为是哪篇情感小作文。等把题面读完才发现，故事的外壳只是障眼法，骨子里是一道再经典不过的数组区间求和问题。

题目大意是：最近有 n 件让人不爽的事，每件事都有一个正整数"刺痛值"，现在想知道连续 m 件事的刺痛值之和，最小能是多少。翻译成算法语言其实特别干净：给定一个长度为 n 的数组 a，请你求出所有长度为 m 的连续子数组中，和最小的是多少。

这里有两个关键词值得划重点。第一个是"连续"，它意味着我们只能取数组中相邻的一段，不能跳着选，这就把问题限制在了区间求和的范围里。第二个是"固定长度"，窗口大小 m 是定死的，我们关心的不是任意子段，而是恰好包含 m 个元素的所有子段。

如果你刚接触算法竞赛，看到这类题第一反应可能是"这不就是把所有情况列一遍嘛"。没错，这题的 n 数据范围很小，暴力确实能过。但正因为题目小，它特别适合拿来理解两个后续刷题高频使用的基础工具：前缀和与滑动窗口。这篇就按我实际做题的流程来讲，从暴力到优化，每一步都交代清楚为什么这么做。

1.2 输入输出与数据范围分析

标准的输入格式是第一行两个整数 n 和 m，第二行是 n 个整数，代表每个"不爽的事"的刺痛值。输出只需要一个整数，就是连续 m 个刺痛值的最小和。

这题的数据范围是 n ≤ 3000，也就是说数组长度最多三千。这个数字看起来很温和，却是决定你选择什么算法的最关键信息。计算一下：如果 m 取中间值 1500，那么可能的连续窗口大约有 1501 个，每个窗口累加 1500 个数，总共约 225 万次加法运算。哪怕是 n 和 m 都取到上限的最坏情况，总运算量也只有几百万级别，现代 CPU 处理这个规模的循环几乎是瞬时的。

所以从纯"过题"的角度讲，你哪怕写一个最朴素的两层循环，也能轻松通过所有测试点。但我的建议是，不要因为能过就不思考。这道题真正的价值在于，它同时适合三种写法的教学：暴力枚举、前缀和、滑动窗口。同一道题用三种思路各写一遍，你对区间求和问题的理解会比刷十道同类题都深刻。

2. 暴力枚举：不需要思考但必须理解的第一版

2.1 枚举起点累加窗口的写法

先看最直白的思路。既然要找所有长度为 m 的连续子段，那就枚举每个可能的起点 i，从 i 开始往后数 m 个数，把它们加起来，跟当前最小值比较。起点 i 的范围是 0 到 n-m，因为一旦起点太靠后，剩下的元素就不够凑满一个窗口了。

cpp复制#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 3005;
int a[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = INT_MAX;
    for (int i = 0; i + m <= n; i++) {
        int sum = 0;
        for (int j = i; j < i + m; j++) {
            sum += a[j];
        }
        if (sum < ans) ans = sum;
    }

    cout << ans << endl;
    return 0;
}

这段代码里唯一的注意点是外层循环的终止条件。我习惯写成 i + m <= n，这样当 i 移动到最后一个合法起点时，内层循环的 j 恰好覆盖到数组末尾，不会越界。如果你改成 i < n - m + 1，效果完全一样，挑自己顺眼的写法就行。

2.2 复杂度为什么会是 O(nm)

暴力解法的复杂度很好分析。外层循环最多有 n-m+1 次，每次内层循环固定执行 m 次加法，所以总操作数约等于 (n-m+1) × m，数量级写作 O(nm)。

这个复杂度在 n ≤ 3000 的时候没什么压力，但你要在心里有个数：同样的代码，如果哪天数据范围改成 n ≤ 100000，这个写法就会直接超时。到那时候，你就需要下面要讲的两个 O(n) 思路。所以暴力写法不是拿来应付比赛的最终答案，而是你验证优化算法正确性的一把尺子——后面自测的时候，我们要反复用它来和优化版对拍。

还有一个细节值得说。暴力代码里我反复强调"先写对，再写快"，是因为在比赛或者刷题场景下，一个验证过正确性的暴力程序非常有价值。当你写出优化版本却样例全过、提交全错的时候，最快定位问题的方法就是用暴力版当裁判，随机生成数据对比输出，几分钟就能锁定是哪里出了偏差。这个习惯我到现在都在用，后面专门讲。

3. 两种O(n)解法：前缀和与滑动窗口

3.1 前缀和把区间和变成两次前缀相减

暴力代码慢在哪里？慢在每次计算窗口和都要重新从头累加。但实际上，我们反复在算同一个数组的不同区间，这里面有大量重复劳动。前缀和的核心思想就是：把"每次现算"变成"提前算好，随时取用"。

具体做法是开一个数组 pre，pre[i] 表示原数组前 i 个元素的和，也就是 pre[i] = a[1] + a[2] + ... + a[i]。有了这个数组之后，任意区间 [l, r] 的和都可以用一次减法得到：sum(l, r) = pre[r] - pre[l-1]。

为什么能这么算？因为 pre[r] 是前 r 个元素的和，pre[l-1] 是前 l-1 个元素的和，两者相减，中间那一段恰好就是区间 [l, r] 的元素，不多不少。

cpp复制#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 3005;
int a[MAXN];
int pre[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    int ans = INT_MAX;
    for (int i = m; i <= n; i++) {
        int sum = pre[i] - pre[i - m];
        if (sum < ans) ans = sum;
    }

    cout << ans << endl;
    return 0;
}

注意我这里数组下标从 1 开始，和暴力版的从 0 开始不同。前缀和用 1-based 下标有个很明显的好处：pre[0] 天然是 0，计算第一个窗口 [1, m] 的和时，pre[m] - pre[0] 不需要特判边界。如果坚持用 0-based，算区间 [l, r] 的时候就得小心 pre[r+1] - pre[l] 这种错位，很容易把自己绕晕。

这段代码的复杂度是 O(n)：预处理前缀和需要一次循环，扫描所有窗口又是一次循环，总共两遍遍历，和暴力版的嵌套循环完全是两个量级。当 n 达到十万甚至百万级别时，前缀和依然是安全的。

3.2 滑动窗口：只加一头减一尾的秘诀

如果说前缀和是"空间换时间"，那滑动窗口就是"通过复用计算结果来减少工作量"。观察一下相邻两个窗口的关系：窗口 [i, i+m-1] 和窗口 [i+1, i+m] 之间有 m-1 个元素是重叠的。也就是说，当我从第一个窗口移动到第二个窗口时，其实只需要在上一窗口和的基础上，加上新滑进来的元素 a[i+m]，再减去滑出去的元素 a[i]，结果就是新窗口的和。

这就意味着，只要我先单独算出第一个窗口的和作为初始值，之后每次右移窗口都只做一次加法和一次减法，窗口的维护成本从 O(m) 降到了 O(1)。整体扫描一遍数组，复杂度 O(n)。

cpp复制#include <iostream>
#include <climits>
using namespace std;

const int MAXN = 3005;
int a[MAXN];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int sum = 0;
    for (int i = 0; i < m; i++) {
        sum += a[i];
    }
    int ans = sum;

    for (int i = m; i < n; i++) {
        sum += a[i];
        sum -= a[i - m];
        if (sum < ans) ans = sum;
    }

    cout << ans << endl;
    return 0;
}

用个生活化的比喻：滑动窗口就像你看火车从面前驶过，想知道任意连续 m 节车厢的总重量。你不需要每来一节车厢就把整车重新称一遍，只需要记住当前这 m 节的总重，车往前走一节，加上新进入视野的那节，减去刚好离开视野的那节，新的总重立刻就有了。

这里最容易写错的是减去的下标。当循环变量 i 从 m 开始递增时，新加进来的是 a[i]，滑出去的是 a[i-m]。我见过不少新手把减去的下标写成 i-m+1，结果窗口长度变成了 m+1 或 m-1，答案自然不对。只要记住"先加新，再减旧，窗口始终保持 m 个元素"，这个顺序就不会乱。

3.3 选哪种：代码量、内存与思维难度对比

把三种写法放在一起比较，结论其实很明显：

对于 P1614 这题，三种写法都能通过。但如果题目把 n 放大到十万甚至百万，暴力就完全不可行了，滑动窗口和前缀和依然是安全的。两者之间怎么选？我的个人习惯是这样：如果题目只是求固定长度区间和的最值，我优先写滑动窗口，因为它不占额外数组，代码也更贴近"维护窗口"的直觉；如果题目后续还要多次查询不同区间的和，那就必须上前缀和，因为滑动窗口只适合处理连续移动的窗口，而前缀和可以任意组合查询区间。

从算法学习的角度，我建议你这一题三种都写一遍，提交三次。不是为了刷提交记录，而是让自己亲身体会"同一个问题，不同复杂度的解法分别长什么样"。这种对比带来的理解，比背十遍模板都扎实。

4. 最容易翻车的边界情况与初始化细节

4.1 窗口长度为1和等于n的极端场景

很多人在示例数据上跑得好好的，一提交就出现奇奇怪怪的 WA，十有八九是边界情况没有考虑到。这道题最典型的两个边界就是 m=1 和 m=n。

m=1 的时候，每个"窗口"只有一个元素，问题退化成"求数组的最小值"。三种写法都能正确处理：暴力版的每个窗口和就是 a[i] 本身；前缀和版的窗口和是 pre[i]-pre[i-1]；滑动窗口版的初始 sum 就是 a[0]，之后每次加一个新元素减一个旧元素，实质上在遍历所有元素取最小。

m=n 的时候，整个数组只有一个窗口，答案就是全数组的和。这时候滑动窗口代码的初始循环会把所有元素加进 sum，主循环一次都不执行，ans 保持初始值，直接输出正确结果。这个天然的正确性正是我把 ans 初始化为第一个窗口和的原因。如果你把 ans 初始化为一个很大的数再进主循环更新，同样没问题，但要小心别初始化成 0 或负数。

4.2 累加和会不会爆int

这类问题看似不起眼，实际是比赛中最坑人的位置之一。本題 n ≤ 3000，每个刺痛值是正整数，假设每个值最大不超过一万，那么最大窗口和也就是三千万量级，普通 int 完全装得下。所以这道题用 int 不会出问题。

但我还是要多说一句：一旦你开始做数据范围更大的题目，累加和爆 int 是最常见的隐蔽错误。正数的累加还算直观，一旦题目里出现负数、或者数据范围达到 10^9 级别，int 就很容易被绕过。我的习惯是，只要题目没有明确说"所有数的和不超过 int 范围"，我就直接用 long long，apart from多占 4 个字节，几乎没有任何代价。OJ 不会因为你多用了点内存就判你错，但会因为 int 溢出让你白白交好几发。

4.3 最小值初始化为什么不能用0

这是我在评论区里看到过很多次的问题：为什么 ans 的初始值要是 INT_MAX，不能是 0？

原因很简单。如果数组里全是正数，那么所有窗口和都是正数，把 ans 初始化成 0 的话，任何窗口和都不会比 0 小，最终答案就会错误地输出 0。这题故意把刺痛值设为正整数，就是为了让这种错误能稳定复现——你一旦把初始值写成 0，样例都能过，但所有测试点都会 WA。

正确做法有两个：一是初始化为 INT_MAX（或更大的值），保证第一个窗口和一定能更新它；二是在滑动窗口版本里，直接用第一个窗口的和作为 ans 的初始值，这样连 INT_MAX 都不用引入，思路也更干净。我两种都写过，实际做题更推荐第二种，因为它顺便把空窗口的诡异情况也规避了。

5. 样例过了还WA？按照这个思路自测

5.1 手动构造小数据验证

样例数据只能证明你的代码在"恰好这一组"输入下是对的，不等于在所有输入下都对。刷题老手都知道，过样例只是起点，真正的考验是边界数据和随机数据。

我常用的第一个自测手段是手动构造几组特殊数据。比如构造 n=5, m=2，数组为 3 1 4 1 5，那么所有窗口和分别是 3+1=4、1+4=5、4+1=5、1+5=6，最小是 4。再用前面提到的极端数据：m=1 时找最小值，m=n 时算总和，如果这些用例的输出都和手算一致，基本可以放心一大半。

如果连这关都没过，先别急着改代码，拿笔在纸上把窗口移动的过程画一遍。我遇到过不少情况是代码逻辑"看起来没问题"，实际跑的时候加数和减数的顺序反了、窗口长度变了。画一遍比盯屏幕半小时有效得多。

5.2 用对拍快速定位错误

手动构造的数据毕竟有限，覆盖面不够。更系统的做法是对拍：写一个随机数据生成器，让暴力程序和优化程序跑同一批数据，对比输出是否一致。只要不一致，就说明优化版在某些输入下算错了，再顺着那组数据去 debug。

对拍的一个完整流程是：先生成一个随机 n、m 和数据数组，把同样的输入分别喂给暴力程序和待测程序，比较两者的输出。暴力程序慢一点没关系，反正它只用来验证小数据。数据规模控制在 n ≤ 20、m ≤ n 就行，跑几千组随机数据，基本能把所有逻辑漏洞都逼出来。

我自己的习惯是，这类基础题在第一次写优化算法时，一定做一次对拍。不是为了这道题，而是为了验证"我理解的滑动窗口逻辑是对的"。等对拍通过之后，以后再遇到类似题，直接写滑动窗口就有底气了。

6. 从P1614延伸：识别"定长连续子段"类问题

6.1 这类题目的三个特征

做完一道题，如果它就只是一道题，那最多算刷了个数量；如果你能总结出"这类题长什么样"，才算把题目价值压榨干净。P1614 代表的是"定长连续子段"问题的基本款，识别特征有三个：

第一，题目中出现"连续"或"相邻"这类词，意味着取的是数组的一段，不能重新排序或跳跃选择。第二，出现"固定长度"或"连续 m 个"这类限制，窗口大小是预先给定的常量。第三，要求计算的是"和的最小值"或类似的最值，本质是在所有固定长度的子段上做扫描。

只要同时满足这三点，滑动窗口就是第一直觉解法。但要注意，如果窗口大小不是固定的，而是要你求"最大子段和"，那就不能用滑动窗口了，得换动态规划或者 Kadane 算法那一套思路。所以特征判断最重要的一步是看窗口长度是不是定值。

6.2 进阶方向从这道题铺开

以 P1614 为起点，可以往几个方向延伸。第一个方向是把最小值换成最大值，代码几乎不用改，就是把判断符号反过来。第二个方向是处理环状数组，把数组复制一份接到后面，长度翻倍，然后用滑动窗口处理，常见于"环形街道上的连续店铺营业额"这类变体。第三个方向是当窗口条件从"固定长度"变成"满足某个条件的最短/最长区间"时，双指针和单调队列就该登场了。

从更宏观的角度看，滑动窗口是双指针技巧的一个分支，而双指针又是很多面试题和竞赛题的解题骨架。你在 P1614 上练熟的"维护一个动态区间、O(1) 更新状态"的感觉，后面会反复用到。

我在实际做题中的体会是，一道题的三种解法里，最容易忽略的不是最难的滑动窗口，反而是那个"慢但一定对"的暴力。很多人一上来就想着写最优解，样例过了就交，结果 WA 了不知道去哪 debug。如果你肯多花十分钟，用暴力版当参照做一次对拍，很多无谓的提交都能省下来。这个习惯，才是比这道题本身更值得带走的东西。