第 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] 0pre[i] 表示 nums 前 i 个元素的和即pre[i] nums[0] nums[1] ... nums[i-1]那么任意子数组 nums[l..r] 的元素和就可以表示为 pre[r1] - pre[l]。接下来把“中心”的条件改写。对于子数组 nums[l..r] 和中心 p左侧区间是 nums[l..p-1]右侧区间是 nums[p1..r]左侧和 pre[p] - pre[l]右侧和 pre[r1] - pre[p1]条件是左右相等pre[p] - pre[l] pre[r1] - pre[p1]把两边整理一下把 l 和 r 相关的项移到一边把 p 相关的项移到另一边pre[l] pre[r1] pre[p] pre[p1]注意到 pre[p1] pre[p] nums[p]所以右侧可以进一步化简pre[p] pre[p1] 2 * pre[p] nums[p]于是核心等式就出来了pre[l] pre[r1] 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[r1] 在不在 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(vectorint nums) { int n nums.size(); vectorlong 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_setlong 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^9n 到 10^5那么前缀和最大可以到 10^14int 直接溢出。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[r1] 完全可能是负值哈希集合对这种值天然友好不需要额外判断。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 自制测试用例表没有测试的算法博客是不完整的。我把自己在验证时用的一组用例整理成了表格可以直接复制去跑nums预期结果手算原因[1, 2, 1]1唯一长度 3 子数组中间元素 2左右都是 1[0, 0, 0, 0]3长度 3 两个长度 4 一个按子数组个数计[1, 2, 3, 4]0没有任何左右和相等的位置[1, -1, 1]1中间 -1左右都是 1负数也能当中心[1, 2, 3, 2, 1]1整体数组中心下标 2左侧 123右侧 213[2, 1, 1, 2, 2]2[1,1,2?] 需手算确认可留给读者验证第六个用例是我随机凑的主要用来自测答案可以在本地跑一遍。关键不是数字有多复杂而是覆盖了正数、负数、零、全相等和递增无解这几类典型情况。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 就固定死了反而更简单。核心思路不变变的只是合法范围。这也是为什么推导等式比背代码重要只要等式在手改边界就是改一个循环起点的事。最后一句话送给正在刷周赛的朋友这种计数题最忌讳一上来就三重循环最划算的投资永远是先花一分钟把数学条件写清楚。中心子数组也好其他“某某子数组的数量”也好等式一旦摆在纸上数据结构和复杂度基本就跟着定下来了。我自己就算这次周赛没写出最优解也会在赛后把这类推导当成固定的复盘内容因为下一次大概率还会碰到相似的题型。