求子数组和的问题，什么时候用前缀和、什么时候用滑动窗口？
简化版
分水岭是数组有没有负数。滑动窗口依赖「扩窗口和增、缩窗口和减」的单调性,所以只适用于全非负数组,擅长「和 ≥ target 的最短子数组」「和恰好为 target 的定长/变长窗口」。前缀和(+ 哈希) 不依赖单调性,有负数也能用,擅长「和恰好为 K 的子数组个数」「和能被 K 整除」这类求个数或存在性的问题。有负数 → 前缀和;全非负 + 求最短/最长连续段 → 滑动窗口。
详细版
| 维度 | 滑动窗口 | 前缀和(+哈希) |
|---|---|---|
| 前提 | 数组非负(需单调性) | 无(可有负数) |
| 擅长 | 和 ≥/≤ target 的最短/最长子数组、定长窗口 | 和 == K 的子数组个数、和被 K 整除、异或为 K |
| 依赖 | 窗口和的单调性 | 「两前缀差为定值」的等式 + 哈希 |
| 时间 | O(n) | O(n) |
| 空间 | O(1)~O(k) | O(n)(哈希) |
完整版教学
一、两种工具解决的是不同形态的问题
前缀和和滑动窗口都能处理「子数组和」问题,但擅长的问题形态不同,不是简单的替代关系:
- 滑动窗口:维护一个动态区间,适合「求满足条件的最短/最长连续子数组」——它天然对应「一段连续区间」的最优化。
- 前缀和 + 哈希:把「区间和」转成「两个前缀和之差」,适合「和恰好为某值的子数组有多少个 / 存不存在」——它擅长计数和存在性。
看到「最短/最长连续段」优先想滑窗;看到「和为定值的个数」优先想前缀和 + 哈希。
二、决定性因素:有没有负数(核心)
选型最硬的标准是数组是否可能有负数:
- 滑动窗口靠单调性:它根据「当前窗口和 vs target」决定扩还是缩,这要求「扩窗口(加元素)和一定不减、缩窗口(移元素)和一定不增」。只有全部非负时这个单调性才成立。
- 有负数:加一个负数会让和变小、移一个负数会让和变大,单调性被打破——滑动窗口无法判断该扩还是该缩,直接失效。这时必须用前缀和 + 哈希,因为它靠的是「
prefix[r] - prefix[l] = K」这个恒等式,和正负无关。
所以一道「子数组和」题,先问:数组会不会有负数?有负数,滑窗出局,用前缀和。
三、典型题的归类
滑动窗口(全非负):
- 长度最小的子数组(和 ≥ target 的最短):非负,滑窗 O(n)。
- 和为 target 的定长/变长窗口:非负时滑窗。
- 无重复最长子串、最多 K 个不同字符:窗口内元素性质单调。
前缀和 + 哈希(可有负数 / 求个数):
- 和为 K 的子数组个数:有负数,滑窗不行,前缀和 + 哈希。
- 和能被 K 整除的子数组:前缀和余数 + 哈希。
- 连续数组(0/1 等量):0 当 -1,前缀和 + 哈希。
四、一个对比例子
同样是「和为 K 的子数组」:
- 如果题目保证数组全为正数,求「和为 K 的最短子数组」→ 滑动窗口 O(n)、O(1) 空间(和太大缩左、太小扩右)。
- 如果数组可能有负数,求「和为 K 的子数组个数」→ 前缀和 + 哈希 O(n)、O(n) 空间(滑窗完全用不了)。
同一个「和为 K」,因为「有无负数」和「求最短还是求个数」的不同,用了完全不同的工具。这就是选型的精髓。
五、前缀和还能配合别的结构
前缀和不只配哈希,还能配其它工具解决更复杂的变体:
- 前缀和 + 二分:非负数组求「和 ≥ K 的最短子数组」,前缀和递增有序,可二分(虽然滑窗更优,但思路通用)。
- 前缀和 + 单调队列:有负数求「和 ≥ K 的最短子数组」(滑窗失效时的正解)。
- 前缀和 + 0-1 Trie:前缀异或求最大异或子数组。
前缀和是「把区间转成两点差」的通用桥梁,配不同结构解不同问题。
六、选型决策流程
面对一道子数组和的题,按这个顺序判断:
- 数组有负数吗? 有 → 排除滑动窗口,用前缀和(+哈希/单调队列)。
- 求什么? 求「和为定值的个数/存在」→ 前缀和 + 哈希;求「满足条件的最短/最长连续段」→ 滑动窗口(非负时)。
- 要不要多次区间查询? 静态数组多次查区间和 → 前缀和;区间批量更新 → 差分。
七、从公式证明到手算闭环
这道题成立的核心是：前缀和保存任意历史边界信息；滑动窗口则依赖指针单向移动时能安全丢弃左端。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。
prefix: sum(l,r)=P[r+1]-P[l]
window: right 扩张更新状态，条件满足或破坏时单调移动 left带数字推演：[2,-5,6] 中右扩加入 -5 会让和下降，普通“和大就缩”的滑窗失效；前缀差仍精确成立。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。
| 核对维度 | 本题结论 |
|---|---|
| 正确性依据 | 前缀和保存任意历史边界信息；滑动窗口则依赖指针单向移动时能安全丢弃左端 |
| 复杂度 | 静态区间查询选前缀和；正数连续区间最短/最长常选滑窗；精确计数与负数常选前缀+哈希 |
| 关键边界 | “有负数”不是所有滑窗都失败，而是基于和的单调窗口失败；定长窗口仍可用；求计数/精确和常需前缀加哈希 |
记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。
八、实现边界与测试策略
实现时最需要警惕的是：“有负数”不是所有滑窗都失败，而是基于和的单调窗口失败；定长窗口仍可用；求计数/精确和常需前缀加哈希。这不是语法细节，而是决定算法是否仍满足题目语义的前提。
提交前应分别验证：
- 空数组或最小合法规模，确认哨兵位置和初始化。
- 查询或更新紧贴左、上边界，确认没有访问负下标。
- 查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
- 包含 0、负数或重复前缀的样例，确认频次与取模语义。
- 大数输入，确认累计和、乘积或答案数量的整数类型足够。
如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。
九、常见误区与追问
- 误区：看到子数组就应该用滑动窗口。 必须先确认窗口推进具有单调性。
- 误区：有负数时任何滑窗都不能用。 定长窗口或其他可维护条件仍可用。
- 误区：前缀和只能做区间查询。 还可配合哈希、单调队列、取模和二分解决计数与优化题。
- 追问：正数最短和为何适合滑窗？ 右扩只增和、左缩只减和，可安全排除状态。
- 追问：和为 K 且含负数怎么做？ 用前缀和频次寻找当前 sum-K。
- 追问：两者空间如何比较？ 基础滑窗常 O(1)，前缀数组/哈希通常 O(n)，但目标能力不同。
十、加强记忆
子数组和问题选型,分水岭是有没有负数:滑动窗口靠「扩窗和增、缩窗和减」的单调性,只适用非负数组,擅长「和 ≥/≤ target 的最短/最长连续段」;前缀和 + 哈希不依赖单调性、有负数也能用,擅长「和为 K 的子数组个数、能被 K 整除、异或为 K」。决策:有负数 → 前缀和;非负 + 求最短/最长段 → 滑窗;求和为定值的个数 → 前缀和 + 哈希。有负数求最短段用前缀和 + 单调队列。