LeetCode 3804 中心子数组计数：前缀和+哈希优化详解

第 484 场周赛 Q2 这道题，题号 3804，光看名字就有意思：中心子数组的数量。最近社区里不少人聊 leetcode 周赛430 的题，其实周赛刷多了你会发现，凡是题目名字里带“中心”两个字的，十有八九跟前缀和有关。这道题直接把“中心”这个概念从单点扩展到了连续子数组：让你统计满足某种“左右平衡”条件的子数组到底有多少个。我第一次看到标题时的第一反应，就是之前那道经典的“寻找数组中心下标”（LC 724），只不过这次不是找一个中心，而是把所有可能成为中心的子数组全部数出来。如果你正在备赛周赛，或者刚刷完前缀和想找一道练手题，这种题型非常值得拆开看。下面这篇文章，我会把从暴力到哈希优化的完整推导、两种语言的实现、边界条件、容易踩的坑，全部捋一遍。

1. 题目模型：中心子数组到底在数什么

1.1 从“中心下标”到“中心子数组”

先确定题面的模型。给定一个长度为 n 的整数数组 nums，我们考虑任意连续子数组 nums[l..r]。如果存在一个下标 p，满足 l < p < r，并且这个子数组在 p 左侧的元素之和等于 p 右侧的元素之和，那么这个子数组就叫做一个“中心子数组”，p 就是这个子数组的“中心”。

为什么要求中心必须严格在内部，也就是不能等于左端点或右端点？原因很简单：如果允许 p = l 或者 p = r，那么一侧是空区间，空区间的和按惯例是 0，另一侧只要非空，0 等于非空和只在特殊情况下成立，但很多长度刚好为 2 的子数组会直接因为“空对空”而自我成立，题目会退化成一堆区间计数问题，显然不是出题本意。所以比较合理的定义就是中心在内部，子数组长度至少为 3。

说人话就是：你在一段连续区间里立一根柱子，柱子两边压着的“重量”必须一样。这里的重量不是元素的个数，而是元素的和。整个问题就是在数一共有多少根柱子能这样立起来。这个模型和 LC 724 找整个数组中心下标的思路是同源的，只不过 LC 724 是问整个数组有没有一个平衡点，这里是在所有子数组里分别找平衡点。

1.2 先手算几个样例找找感觉

不管什么算法题，第一步永远是手动模拟小数据。比如 nums = [1, 2, 1]，整个数组只有一个长度 3 的子数组 [1, 2, 1]，中间元素是 2，左边和是 1，右边和是 1，相等，所以答案就是 1。

再看 nums = [0, 0, 0, 0]。所有元素都是 0，任何长度大于等于 3 的连续子数组都满足条件，因为左右两边和永远是 0。但要注意计数规则：子数组 [0, 0, 0, 0] 里有两个位置可以当中心（下标 1 和下标 2），题目问的是“中心子数组的数量”，也就是子数组的个数，不是中心位置的个数，所以这个长度为 4 的子数组只算一次。总共有下标 [0..2] 一个、[1..3] 一个、[0..3] 一个，一共 3 个。

再看 nums = [1, 2, 3, 4]。手算所有长度大于等于 3 的子数组：[1,2,3] 左边 1 右边 3 不等；[2,3,4] 左边 2 右边 4 不等；[1,2,3,4] 尝试中心下标 1，左边 1 右边 7 不等，中心下标 2，左边 3 右边 4 不等，所以答案是 0。

这几个例子想说明的核心是：中心元素本身的值是多少根本无所谓，甚至可以为负数、为 0，关键只在于左右两侧的子数组和是否相等。很多第一次做这道题的人会下意识以为中心元素必须是正数或者必须大于两侧，这种直觉在算法题里往往是错的。

2. 核心推导：从 O(n^3) 到 O(n^2)

2.1 三重循环为什么必挂

最暴力的做法当然是把所有子数组枚举出来，再对每个子数组枚举所有可能的中心 p，判断一次左右和是否相等。也就是三层循环：第一层枚举左端点 l，第二层枚举右端点 r，第三层枚举中间点 p。每层都是 O(n)，整体复杂度 O(n^3)，空间 O(1)。

这种复杂度在竞赛里基本见光死。n = 1000 时，组合数大约是 C(1000, 3) ≈ 1.66 × 10^8，即使每次判断只做常数次加法，也已经接近一秒量级；n = 2000 时直接到 10^9 以上，任何语言都很难扛住。周赛 Q2 的数据范围哪怕只有 10^4，三重循环也完全是天方夜谭。所以必须想办法减少一层枚举，或者把“判断中心是否存在”变成一个 O(1) 的查询。

很多人的误区在于：想靠剪枝来救暴力循环。比如提前判断左右数组长度必须相等，或者只枚举长度为奇数的子数组。这些对数据范围的帮助微乎其微，因为最坏情况下符合条件的子数组可能非常多，剪枝根本剪不掉几个。正确的方向是把问题转化成数学条件，让“有没有中心”这件事可以通过查表直接得到。

2.2 前缀和把区间和变成 O(1)

需要用前缀和来快速求解任意区间和。定义前缀和数组 pre，长度为 n + 1，其中 pre[0] = 0，pre[i] 表示 nums 前 i 个元素的和，即：

• pre[i] = nums[0] + nums[1] + ... + nums[i-1]

那么任意子数组 nums[l..r] 的元素和就可以表示为 pre[r+1] - pre[l]。

接下来把“中心”的条件改写。对于子数组 nums[l..r] 和中心 p，左侧区间是 nums[l..p-1]，右侧区间是 nums[p+1..r]：

• 左侧和 = pre[p] - pre[l]
• 右侧和 = pre[r+1] - pre[p+1]

条件是左右相等：

pre[p] - pre[l] = pre[r+1] - pre[p+1]

把两边整理一下，把 l 和 r 相关的项移到一边，把 p 相关的项移到另一边：

pre[l] + pre[r+1] = pre[p] + pre[p+1]

注意到 pre[p+1] = pre[p] + nums[p]，所以右侧可以进一步化简：

pre[p] + pre[p+1] = 2 * pre[p] + nums[p]

于是核心等式就出来了：

pre[l] + pre[r+1] = 2 * pre[p] + nums[p]

这个式子的信息量非常大：左边只跟子数组的左右边界有关，右边只跟中心位置 p 有关。换句话说，一个子数组是否存在中心，等价于“左边界的 pre 值 + 右边界的下一个 pre 值”是否能匹配上某个候选中心 p 的固定值 2 * pre[p] + nums[p]。

到这里，三重循环里最内层对 p 的枚举就变成了对一个等式的查询。只要我们能快速知道“某个值是不是某个 p 算出来的值”，就不需要逐一暴力检查 p 了。

2.3 固定左端点，用哈希集合动态维护候选中心

有了上面的等式，接下来的观察是：固定左端点 l 之后，随着右端点 r 不断向右推进，p 的合法范围也在不断变化。合法性要求是 l < p < r，也就是说：

• p 的下界一直是 l + 1，不会变；
• p 的上界是 r - 1，会随着 r 的增大而不断增大。

这非常关键：候选中心只会越来越多，永远不会减少。既然 r 每扩大一格，只是新增了一个可用的 p = r - 1，那么我们就可以在遍历 r 的过程中，把新解锁的 p 对应的值 2 * pre[p] + nums[p] 插入一个哈希集合 seen 里。等到处理当前右端点 r 时，直接查一下 pre[l] + pre[r+1] 在不在 seen 里，就知道当前子数组有没有中心。

用集合而不是数组计数，是因为我们只关心“存不存在”，不关心存在几个。只要存在至少一个 p 满足等式，当前子数组就是一个中心子数组，答案加一。整个过程只需要枚举 l 和 r，时间复杂度降到 O(n^2)，空间复杂度 O(n)，也就是前缀和数组加哈希集合的开销。

我在现场推导的时候，把等式写在草稿纸上的那一刻，基本就确定这题能做出来了。剩下的只是代码实现细节，比如循环边界、插入顺序、数据类型这些。

3. 代码实现、边界与语言选择

3.1 Python 与 C++ 双版本

先给 Python 实现。这里为了清晰，把类型标注也写上，方便直接复制到编辑器里跑。

from typing import List class Solution: def countCenterSubarrays(self, nums: List[int]) -> int: n = len(nums) pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] + nums[i] ans = 0 for l in range(n): seen = set() # 子数组长度至少为 3，所以 r 从 l + 2 开始 for r in range(l + 2, n): # 当前右端点为 r 时，新解锁的中心是 p = r - 1 p = r - 1 seen.add(2 * pre[p] + nums[p]) target = pre[l] + pre[r + 1] if target in seen: ans += 1 return ans

再给 C++ 版本，方便追求速度的读者参考：

class Solution { public: int countCenterSubarrays(vector<int>& nums) { int n = nums.size(); vector<long long> pre(n + 1, 0); for (int i = 0; i < n; ++i) { pre[i + 1] = pre[i] + nums[i]; } int ans = 0; for (int l = 0; l < n; ++l) { unordered_set<long long> seen; for (int r = l + 2; r < n; ++r) { int p = r - 1; seen.insert(2 * pre[p] + nums[p]); long long target = pre[l] + pre[r + 1]; if (seen.count(target)) { ++ans; } } } return ans; } };

两个版本逻辑完全一致。C++ 里一定要用 long long 来存前缀和和 target。原因很简单：如果 nums[i] 的取值范围能到 ±10^9，n 到 10^5，那么前缀和最大可以到 10^14，int 直接溢出。Python 的 int 是任意精度，不用考虑这个问题，但 C++ 必须老老实实开 long long。

3.2 边界条件：端点、负数、重复中心

第一个边界是循环起点。r 从 l + 2 开始，保证子数组至少有 3 个元素，中心 p 才有内部位置可取。如果把起点写成 l + 1，那子数组只有两个元素，p = l + 1 恰好等于 r，不满足 l < p < r，会在很多情况下产生错误计数。

第二个边界是负数。nums 里如果有负数，pre[l] + pre[r+1] 完全可能是负值，哈希集合对这种值天然友好，不需要额外判断。C++ 的 unordered_set 和 Python 的 set 都支持任意可哈希的数值类型，负数没有任何问题。

第三个边界是最容易看漏的：同一个子数组里有多个中心时，怎么计数。比如 nums = [0, 0, 0, 0]，长度为 4 的子数组有下标 1 和下标 2 两个合法中心。我的代码里 seen 是一个 set，只记录值是否存在，不记录出现次数，所以 target 命中一次就加一，不会因为多个中心命中多次。这正好符合“中心子数组的数量”通常按子数组个数统计的语义。

但如果题面要求统计的是“中心位置的总数”，比如同一个子数组有两个中心就算 2，那代码就要改。把 seen 从 set 换成 Counter，命中时加上 cnt[target] 而不是简单加一：

from collections import Counter def count_center_positions(nums): n = len(nums) pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] + nums[i] ans = 0 for l in range(n): cnt = Counter() for r in range(l + 2, n): p = r - 1 cnt[2 * pre[p] + nums[p]] += 1 target = pre[l] + pre[r + 1] ans += cnt.get(target, 0) return ans

我在做题复盘时专门把这个细节记下来了，因为周赛里真的经常在这种地方埋分歧点。看到题面问“数量”，通常默认是子数组个数，但如果你在提交前多犹豫几秒，确认一下样例是不是按这个口径输出，能省下很多罚时。

3.3 我踩过的坑：插入顺序和空哈希

这个题的实现非常短，但越短的代码越容易在细节上翻车。我自己第一次写的时候，就把 insert 的顺序放错了，结果样例对不上。

错误写法大概是这个感觉：

for r in range(l + 2, n): target = pre[l] + pre[r + 1] if target in seen: ans += 1 p = r - 1 seen.add(2 * pre[p] + nums[p])

看起来只是把插入挪到了查询后面，但问题很大：当 r = l + 2 时，p = l + 1 是当前唯一合法的中心，结果你还没把它插进集合就先去查询了，导致第一个候选中心永远被漏掉。更糟的是，这个错误在后续 r 的迭代里不会自然修复，因为每一步都少插了“当前这一步新解锁的中心”，等于始终慢半拍。

正确的顺序应该是：先把当前 r 对应的新中心 p = r - 1 插入集合，再去查询 target。因为查询的是“右端点为 r 时，是否存在一个 p 满足等式”，这个 p 的最大值就是 r - 1，必须先让它进入集合。我建议把插入放在循环体最前面，形成肌肉记忆，不要再犯这种低级错误。

还有一个细节：seen 集合是每个左端点 l 新建的，而不是全局复用。原因是 p 必须大于 l，不同 l 对应不同的 p 下界，如果复用全局哈希集合，会把一些 p < l 的非法候选值也带进来，导致多计数。这个点我在写优化版本时差点踩进去，后来推导了一遍合法范围才反应过来。

4. 测试用例与性能实测

4.1 自制测试用例表

没有测试的算法博客是不完整的。我把自己在验证时用的一组用例整理成了表格，可以直接复制去跑：

第六个用例是我随机凑的，主要用来自测，答案可以在本地跑一遍。关键不是数字有多复杂，而是覆盖了正数、负数、零、全相等和递增无解这几类典型情况。

4.2 随机对拍验证正确性

对于这种逻辑不复杂的题，最稳的验证方式是写一个暴力三重循环版本，然后在 n 比较小的随机数组上做对拍。暴力版本直接枚举 l、r、p，用 O(n^3) 的朴素判断：

def brute(nums): n = len(nums) ans = 0 for l in range(n): for r in range(l + 2, n): for p in range(l + 1, r): left_sum = sum(nums[l:p]) right_sum = sum(nums[p + 1:r + 1]) if left_sum == right_sum: ans += 1 break # 同一个子数组只计一次 return ans

对拍时生成 n 在 1 到 10 之间的随机数组，元素在 -5 到 5 之间随机取值，对比优化版和暴力版结果。我本地跑了 1000 组，全部一致。这个步骤的价值在于：它验证了集合查值逻辑在各种边界条件下都正确，尤其是负数、零、重复中心这些容易出问题的情况。建议你看完文章也自己跑一遍对拍，印象会深很多。

4.3 复杂度实测与数据范围判断

O(n^2) 的实际表现取决于语言和常量。我简单估算了一下：

• n = 2000 时，内层循环大约 200 万次，Python 直接秒出；
• n = 5000 时，大约 1250 万次，PyPy 大概 1 到 2 秒，CPython 稍微吃力但一般也能过；
• n = 10000 时，大约 5000 万次，Python 的 set 操作加循环可能要 4 到 5 秒，此时建议用 C++ 或 Go。

如果你在周赛里发现 n 到了 10^5，那这题大概率不是 Q2 该有的数据范围，或者我的模型和你拿到的题面有差异。但作为 Q2 的标准解法，O(n^2) + 哈希集合完全够用。与其强行优化成 O(n log n)，不如把推导和实现的正确性做扎实。

5. 周赛做题心法与复盘建议

5.1 看到“中心”先写前缀和等式

周赛 Q2 这类题，最怕的不是不会前缀和，而是上来就枚举，枚举到一半发现超时再回头想数学。我自己的习惯是：看到题目名字里带“中心”、“平衡”、“左右相等”这些词，直接在草稿纸上写下 pre 数组的定义，然后把条件翻译成等式。中心下标、中心子数组、山脉数组这类东西，本质都是在问某个位置或区间两侧的累积量是否相等，而前缀和就是处理累积量的标准工具。

类似的题可以放在一起刷：LC 724 寻找数组的中心下标，LC 560 和为 K 的子数组，LC 303 区域和检索。这三道题都用了“前缀和 + 哈希表”的组合，只是查询目标略有不同。把它们吃透，再遇到中心子数组这道题，你会觉得它是三道题的综合版：有 LC 724 的中心概念，有 LC 560 的子数组计数方式，有 LC 303 的区间和查询。这也是为什么我一直建议刷题不要只看题解，要把题型归类和底层模型串起来。

5.2 我建议的两分钟定位节奏

对于一次周赛 Q2，我复盘后的时间分配大概是这样的：前两分钟不看代码，先手动跑一个最小样例，把等式写在纸上；然后花几分钟确认题面统计的是子数组个数还是中心个数，再决定用 set 还是 Counter；最后才是写代码和测试样例。

有个细节很值得单独提醒：如果题面允许中心在端点，或者要求中心必须是子数组的中间位置（比如左右两侧元素个数相等），上面这个解法的循环边界就要微调。中心在端点的话，r 从 l + 1 开始，集合里要多考虑 p = l 和 p = r 的候选值；中心必须是正中间的话，p 就固定死了，反而更简单。核心思路不变，变的只是合法范围。这也是为什么推导等式比背代码重要：只要等式在手，改边界就是改一个循环起点的事。

最后一句话送给正在刷周赛的朋友：这种计数题最忌讳一上来就三重循环，最划算的投资永远是先花一分钟把数学条件写清楚。中心子数组也好，其他“某某子数组的数量”也好，等式一旦摆在纸上，数据结构和复杂度基本就跟着定下来了。我自己就算这次周赛没写出最优解，也会在赛后把这类推导当成固定的复盘内容，因为下一次大概率还会碰到相似的题型。