leetcode 题解：前缀和与滑动窗口专题——从母题套路到五道实战题

• 文档
• 教程
• 知识库

导读

本文是 leetcode 题解仓库中「前缀和专题」（thinkings/prefix.md）的深度展开。专题以"连续"这一关键字为线索，先用五个递进的母题建立"前缀和 + 滑动窗口"的统一解题套路，再以 467、795、904、992、1109 五道 LeetCode 原题验证套路。读完本文，你将掌握 atMostK 这个"灵魂方法"、exactK / betweenK 的容斥变形，以及前缀和差分区间加法的实战用法，并能把同一套路迁移到仓库中 560、525、1310、1371 等一系列同类题目。

为什么"连续"是这道题的题眼

暴力解是绝大多数连续类题目的起点，但题目一旦出现"连续子数组""连续子串"的限制，就应当条件反射般想到两类优化工具：

• 滑动窗口（Sliding Window）：通过左右指针维护一段连续区间，适合求解与区间内元素集合、计数、最值相关的子数组问题；
• 前缀和（Prefix Sum）：通过预处理"前 n 项之和"把区间求和查询降为 O(1)，适合与区间和、区间差分相关的子数组问题。

二者都服务于同一个目标——优化时间复杂度。因此判断标准非常朴素：能用暴力解出、且题目恰好带有"连续"限制，就应该往滑动窗口和前缀和的方向思考。这与仓库中滑动窗口专题的结论一致："求解'连续子串 xxxx''连续子数组 xxxx'，就应该可以想到滑动窗口"。

前菜：五个母题，搭建统一套路

专题先用五个递进的母题建立"识别套路"的能力，后续四道题全部是母题的变体。前置知识为滑动窗口（模板与伪代码可参考仓库中的滑动窗口专题）。

母题 0：什么是前缀和

有 N 个正整数放在数组 A 里，现在要求一个新数组 B，新数组的第 i 个数 B[i] 是原数组 A 第 0 到第 i 个数的和。

前缀和是一种重要的预处理手段，能大大降低查询的时间复杂度，可简单理解为"数列的前 n 项的和"：数组中第 n 位存储的是数组前 n 个数字的和。

对[1,2,3,4,5,6]来说，其前缀和为pre=[1,3,6,10,15,21]，通过递推公式pre[i] = pre[i-1] + nums[i]即可逐位求出。前缀和概念本身很简单，难点在于如何在题目中识别并运用前缀和——这是整个专题真正的门槛。

仓库中的 560. 和为 K 的子数组 就是前缀和的典型应用：先用pre[j] - pre[i-1]表示任意区间[i, j]的和，再配合哈希表统计pre[j] - k出现次数，即可在 O(N) 内完成计数。入门练习题可做 1480. 一维数组的动态和。

母题 1：连续子数组的总个数

求一个数组连续子数组的总个数，连续指索引连续。如[1,3,4]的连续子数组有[1], [3], [4], [1,3], [3,4], [1,3,4]，返回 6。

一种完备的思路是：总数 = 以索引 0 结尾的子数组个数 + 以索引 1 结尾的子数组个数 + ... + 以索引 n-1 结尾的子数组个数。同时利用母题 0 的"边遍历边累加"思路，参考代码（JS）：

function countSubArray(nums) { let ans = 0; let pre = 0; for (_ in nums) { pre += 1; ans += pre; } return ans; }

复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。

由于以索引 i 结尾的子数组个数就是 i+1，本题也可直接用等差数列求和公式(1 + n) * n / 2（n 为数组长度）。这个"以某个位置结尾计数"的思路是整个专题的骨架。

母题 2：相邻差为 1 的连续子数组个数

求一个数组"相邻差为 1"的连续子数组的总个数，即索引差 1 的同时，值也差 1。

与母题 1 思路类似，只是在遍历时增加对差值是否为 1 的判断：

function countSubArray(nums) { let ans = 1; let pre = 1; for (let i = 1; i < nums.length; i++) { if (nums[i] - nums[i - 1] == 1) { pre += 1; } else { pre = 0; } ans += pre; } return ans; }

复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。

若把"差为 1"改为"差值大于等于 1"，只需改一下符号——这就变成求上升子序列个数了，可作为课后练习自行验证。

母题 3：不大于 k 的子数组个数（atMostK）

求所有元素都不大于 k 的子数组个数。如[1,3,4]不大于 3 的子数组有[1], [3], [1,3]，个数为 3。实现函数atMostK(k, nums)。

function countSubArray(k, nums) { let ans = 0; let pre = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] <= k) { pre += 1; } else { pre = 0; } ans += pre; } return ans; }

复杂度分析：时间复杂度 O(N)，空间复杂度 O(1)。

注意这里的计数技巧：pre记录"以当前位置结尾、且满足条件的最长连续段长度"，遇到不满足条件的元素就清零，ans += pre即等价于"以当前位置结尾的合法子数组个数"。这就是 atMostK 的灵魂。

母题 4：最大值刚好为 k 的子数组个数（exactK）

求子数组最大值刚好是 k 的个数。如[1,3,4]中最大值刚好为 3 的子数组有[3], [1,3]，个数为 2。实现exactK(k, nums)。

exactK 可以直接利用 atMostK 推导：exactK(k) = atMostK(k) - atMostK(k - 1)，原因在母题 5 中说明。

母题 5：最大值介于 k1 和 k2 之间的子数组个数（betweenK）

求子数组最大值介于 k1 和 k2 之间的个数。实现betweenK(k1, k2, nums)。

betweenK 同样由 atMostK 容斥得出：betweenK(k1, k2, nums) = atMostK(k1, nums) - atMostK(k2 - 1, nums)，其中 k1 > k2。其前提是值域离散（例如题目中的整数），此时可以直接减 1，因为1 是两个整数间最小的间隔。

直观理解：小于等于 k1 的区域减去小于 k2 的区域，得到的就是大于等于 k2 且小于等于 k1 的区域。注意是"小于 k2"而非"小于等于 k2"——由于整数离散、最小间隔为 1，小于 k2 等价于小于等于 k2-1，这正是atMostK(k2 - 1)的由来。

由此可看出exactK 是 betweenK 的特殊形式：当 k1 == k2 时，betweenK 退化为 exactK。因此atMostK 是整个专题的灵魂方法，必须重点掌握。

467. 环绕字符串中唯一的子字符串（中等）

题目描述

把字符串 s 看作是"abcdefghijklmnopqrstuvwxyz"的无限环绕字符串，即"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."。给定另一个字符串 p，求 s 中有多少个唯一的 p 的非空子串。p 仅由小写英文字母组成，长度可能超过 10000。

示例：

• 输入"a"，输出 1（s 中只有一个"a"）；
• 输入"cac"，输出 2（s 中只有"a"、"c"两个子串）；
• 输入"zab"，输出 6（"z"、"a"、"b"、"za"、"ab"、"zab"）。

前置知识

• 滑动窗口

思路

s 是固定无限循环串，p 的数据范围是 10^5，暴力枚举所有子串需要约 10^10 次操作，必然超时。仔细审题后发现：这不就是母题 2 的变种么——求相邻字符在环绕串中"连续"（差值为 1 或 -25）的子串长度。为了减少边界判断，可以在 p 前面加一个哨兵字符^。

先看一个有问题的版本（cac会被错误计算为 3，实际应为 2，根因是 c 被重复计算了两次）：

class Solution: def findSubstringInWraproundString(self, p: str) -> int: p = '^' + p w = 1 ans = 0 for i in range(1,len(p)): if ord(p[i])-ord(p[i-1]) == 1 or ord(p[i])-ord(p[i-1]) == -25: w += 1 else: w = 1 ans += w return ans

去重的朴素思路是用 set 记录访问过的子串。而由于 set 中元素一定是连续的，可以用 hashmap 压缩存储：key 为结尾字母，value 为该字母结尾的最长连续子串长度，例如：

{ c: 3 d: 4 b: 1 }

含义是：以 b 结尾的子串最大长度为 1（即 b）；以 c 结尾的最大长度为 3（即 abc）；以 d 结尾的最大长度为 4（即 abcd）。至于中间的 c 无需重复保存，可通过母题 2 的方式推算出来。

具体算法：

1. 定义len_mapper：key 是字母，value 是长度，含义为以 key 结尾的最长连续子串的长度（关键字：最长）；
2. 用变量 w 记录当前连续子串长度，遍历过程中按 w 更新len_mapper（取 max）；
3. 返回len_mapper中所有 value 的和。

该算法不重不漏，因为最长的连续子串一定包含比它更短的连续子串——这一剪枝思想与仓库问题 1297. 子串的最大出现次数 的方法异曲同工。

代码（Python）

class Solution: def findSubstringInWraproundString(self, p: str) -> int: p = '^' + p len_mapper = collections.defaultdict(lambda: 0) w = 1 for i in range(1,len(p)): if ord(p[i])-ord(p[i-1]) == 1 or ord(p[i])-ord(p[i-1]) == -25: w += 1 else: w = 1 len_mapper[p[i]] = max(len_mapper[p[i]], w) return sum(len_mapper.values())

复杂度分析

• 时间复杂度：O(N)，N 为字符串 p 的长度；
• 空间复杂度：最多存储 26 个字母，空间为常数，即 O(1)。

795. 区间子数组个数（中等）

题目描述

给定元素都是正整数的数组 A、正整数 L 和 R（L <= R），求连续、非空且最大元素满足大于等于 L、小于等于 R的子数组个数。

示例：A = [2, 1, 4, 3]，L = 2，R = 3，输出 3（满足条件的子数组：[2], [2, 1], [3]）。

注意：L、R 和 A[i] 都是整数，范围 [0, 10^9]；数组长度范围 [1, 50000]。

前置知识

• 滑动窗口

思路

本题是母题 5 与母题 2 的直接组合：

• 由母题 5：betweenK = atMostK(k1) - atMostK(k2 - 1)（k1 > k2）；
• 由母题 2：已知如何求"元素都满足某条件（这里是小于等于 R）"的子数组个数。

二者结合即可求解，即notGreater(R) - notGreater(L - 1)。

代码（Python）

class Solution: def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int: def notGreater(R): ans = cnt = 0 for a in A: if a <= R: cnt += 1 else: cnt = 0 ans += cnt return ans return notGreater(R) - notGreater(L - 1)

复杂度分析

• 时间复杂度：O(N)，N 为数组长度；
• 空间复杂度：O(1)。

904. 水果成篮（中等）

题目描述

一排树，第 i 棵树产生 tree[i] 型水果。你可以从任意树开始重复：把水果放进篮子，做不到就停止；移动到右侧下一棵树。你有两个篮子，每个篮子可携带任意数量水果，但每个篮子只能装一种类型的水果。求最多能收集多少棵果树。

示例：

• 输入 [1,2,1]，输出 3（可收集 [1,2,1]）；
• 输入 [0,1,2,2]，输出 3（可收集 [1,2,2]，从第一棵树开始只能收集 [0,1]）；
• 输入 [1,2,3,2,2]，输出 4（可收集 [2,3,2,2]）；
• 输入 [3,3,3,1,2,1,1,2,3,3,4]，输出 5（可收集 [1,2,1,1,2]）。

提示：1 <= tree.length <= 40000，0 <= tree[i] < tree.length。

前置知识

• 滑动窗口

思路

抽象题目：给定数组，选定一个最多只有两种数字的子数组，求其最大长度。这不就是母题 3 的变形么——只是 k 变成了固定值 2。由于窗口内要求"最多两种数字"，不能再使用 set，而需要哈希表同时记录窗口内有哪些数字以及每个数字的出现次数，这样才能在窗口收缩时正确维护计数，从而用滑动窗口把时间复杂度优化到 O(N)。

代码（Python）

class Solution: def totalFruit(self, tree: List[int]) -> int: def atMostK(k, nums): i = ans = 0 win = defaultdict(lambda: 0) for j in range(len(nums)): if win[nums[j]] == 0: k -= 1 win[nums[j]] += 1 while k < 0: win[nums[i]] -= 1 if win[nums[i]] == 0: k += 1 i += 1 ans = max(ans, j - i + 1) return ans return atMostK(2, tree)

复杂度分析

• 时间复杂度：O(N)，N 为数组长度；
• 空间复杂度：O(k)，这里 k 为常数 2，实际为 O(1)。

992. K 个不同整数的子数组（困难）

题目描述

给定正整数数组 A，若 A 的某个子数组中不同整数的个数恰好为 K，则称其为好子数组。返回 A 中好子数组的数目。

示例：

• A = [1,2,1,2,3]，K = 2，输出 7（[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]）；
• A = [1,2,1,3,4]，K = 3，输出 3（[1,2,1,3], [2,1,3], [1,3,4]）。

提示：1 <= A.length <= 20000，1 <= A[i] <= A.length，1 <= K <= A.length。

前置知识

• 滑动窗口

思路

由母题 5 直接可得：exactK = atMostK(k) - atMostK(k - 1)。于是答案呼之欲出，其余部分与 904 题（水果成篮）几乎完全一致——事实上它与所有"滑动窗口计数"题目都同构。

代码（Python）

class Solution: def subarraysWithKDistinct(self, A, K): return self.atMostK(A, K) - self.atMostK(A, K - 1) def atMostK(self, A, K): counter = collections.Counter() res = i = 0 for j in range(len(A)): if counter[A[j]] == 0: K -= 1 counter[A[j]] += 1 while K < 0: counter[A[i]] -= 1 if counter[A[i]] == 0: K += 1 i += 1 res += j - i + 1 return res

复杂度分析

• 时间复杂度：O(N)，N 为数组长度；
• 空间复杂度：O(k)。

1109. 航班预订统计（中等）

题目描述

有 n 个航班，编号从 1 到 n。预订表第 i 条记录bookings[i] = [i, j, k]表示在从 i 到 j 的每个航班上预订了 k 个座位。返回长度为 n 的数组 answer，按航班编号顺序给出每个航班上预订的座位数。

示例：bookings = [[1,2,10],[2,3,20],[2,5,25]]，n = 5，输出 [10,55,45,25,25]。

提示：1 <= bookings.length <= 20000，1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000，1 <= bookings[i][2] <= 10000。

前置知识

• 前缀和

思路

题目描述较绕，先分析语义：[i, j, k]表示第 i 站上来 k 个人，一直到第 j 站都在飞机上，到第 j+1 站就不在飞机上了。所以第 i 站到第 j 站的每一站都会因此多 k 个人。据此可先写出暴力版本：

class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: counter = [0] * n for i, j, k in bookings: while i <= j: counter[i - 1] += k i += 1 return counter

内层 while 是"对连续一段数组全部加上一个数"，复杂度太高无法通过全部测试用例。注意到这一点，不难想到用母题 0 的前缀和思路优化：

• 在 i 位置 +k，利用前缀和技巧给 i 到 n 的所有元素都加上 k；
• 但题目要求加的是一段区间[i, j]，若直接前缀和，j+1 及其之后的元素会被多加一个 k；
• 于是再在 j+1 位置 -k，正负相抵，前缀和后区间[i, j]恰好增加 k，其余位置不变。

这就是差分数组 + 前缀和（区间增量问题）的标准做法：差分数组只需在两个端点打标记，最终一次前缀和还原出每个位置的累加值。

代码（Python）

class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: counter = [0] * (n + 1) for i, j, k in bookings: counter[i - 1] += k if j < n: counter[j] -= k for i in range(n + 1): counter[i] += counter[i - 1] return counter[:-1]

复杂度分析

• 时间复杂度：O(N)，N 为数组长度；
• 空间复杂度：O(N)。

总结：套路如何迁移到更多题目

五道题贯穿同一条主线：滑动窗口负责"连续计数"，前缀和负责"区间求和/区间增量"，两者套路固定、有模板可套。真正的难点在于"如何想到用这个技巧"。专题给出两点方法论：

1. 找关键字：题目出现"连续"，就条件反射想到滑动窗口和前缀和；题目求最大最小，就想到动态规划和贪心。想到之后再与题目信息对比，快速排除错误算法、锁定可行解——这种"题感"会随着刷题量增加而变强。
2. 先写暴力解，再找瓶颈：写出暴力解后分析瓶颈所在，根据瓶颈自然推导出该用何种数据结构与算法优化。例如 1109 题暴力内层 while 是区间逐个加 k，瓶颈在"连续区间批量加"，于是自然引出差分前缀和。

延伸练习（仓库内配套题解）

下列仓库题目与本文套路同源，建议独立完成：

• 303. 区域和检索 - 数组不可变——前缀和经典入门；
• 560. 和为 K 的子数组——前缀和 + 哈希表计数；
• 525. 连续数组——把 0/1 转为 -1/1，前缀和求最长零和区间；
• 1310. 子数组异或查询——前缀异或（异或的"前缀和"）；
• 1371. 每个元音包含偶数次的最长子字符串——状态压缩 + 前缀和的进阶组合；
• 1186. 删除一次得到子数组最大和——连续子数组与动态规划的组合。

更多滑动窗口题目与模板代码可继续阅读仓库的滑动窗口专题，以及 209. 长度最小的子数组 等配套题解。

• 文档
• 教程
• 知识库