星期六爬起来打周赛的人都有一种默契题可以不会但一定要知道它卡在哪。第484场周赛的Q2题号3804标题是“中心子数组的数量Count the Number of Centered Subarrays”。这个题名本身就有迷惑性我一开始差点按“回文子串”去处理结果审完题发现完全是另一码事它不是判断左右对称而是在比左右两段元素和。如果你也习惯性地往中心扩展、回文匹配那边想这篇文章值得看完。我会把题目拆成数学条件给出可以直接抄的Python解法再把赛场上看不见的边界情况和坑一并说清楚。1. 从题意切入中心子数组到底在比较什么1.1 把“中心”翻译成数学语言题目里的“中心”官方定义是一个下标k但不是随便拿个下标就能当中心。它要满足一个非常具体的条件子数组nums[l..r]以k为中心时左侧那一段nums[l..k-1]的元素和必须等于右侧那一段nums[k1..r]的元素和。写成式子更直观sum(nums[l..k-1]) sum(nums[k1..r])这里l和r分别是子数组的左端点和右端点满足l k r。注意几个容易忽略的细节第一左右两段允许为空所以单个元素组成的子数组天然满足条件因为空集的和是0两边都是0第二题目限定左右两段长度相同也就是说k必须是子数组的正中间那个位置不存在“偏向左边一个元素”这种偷懒的中心第三这里的比较是元素和相等不是元素值镜像相等所以拿“回文”的思路去套会直接跑偏。我第一次做这个题时心里os是“这不就是中心扩展模板题吗”结果仔细一算才发现回文中心扩展验证的是nums[k-d]nums[kd]而这里验证的是两段区间的总和。一个是逐位比较一个是区间求和差的不是一星半点。这也提醒我周赛Q2这类题命名往往会引导你走向某个熟悉的套路但真正决定难度的反而是那句看似平淡的条件描述。1.2 一个例子把答案算明白光说定义不够直观我用手算一个例子。nums [1, 2, 1]逐个数一下中心子数组中心k0子数组[0,0]左右都为空左右和都是0成立。中心k1子数组[1,1]左右都为空成立。中心k1子数组[0,2]左段是nums[0..0][1]和是1右段是nums[2..2][1]和是1相等成立。中心k2子数组[2,2]左右都为空成立。所以答案是4。这里没有别的组合了比如子数组[1,2]它不是奇数长度根本不存在一个整数下标k能当正中间子数组[0,1]同理。这个例子说明一点按题目的“中心”定义其实只考虑奇数长度的子数组。这个结论后面写代码时会省掉很多重复判断。再看一个稍微复杂的数组[1, 2, 3, 2, 1]k2d1左段[1]和2右段[1]和2相等成立。k2d2左段[1,2]和3右段[2,1]和3相等也成立。同一个中心下有两层满足条件这说明一个关键点找到一组相等之后不能立刻break必须继续往外扩展。这个坑我在后面会专门再讲。先把结论记住它是本题正确率下降的元凶之一。2. 别急着写中心扩展先想清楚统计逻辑2.1 为什么不能先枚举区间再找中心很多人的第一反应是暴力枚举所有子数组然后对每个子数组找它中间那个位置判断左右和是否相等。这个思路不是不能用但复杂度很难看。枚举所有子数组O(n²)再对每个子数组计算左右两段的和哪怕用前缀和把求和降到O(1)总复杂度也是O(n²)。有人觉得O(n²)还行但实际比赛里n往往给你放到10的五次方量级O(n²)直接超时。更关键的问题在于先枚举区间再找中心会带来重复计算。比如数组[0, 1, -1, 0]里子数组[0,3]以0为中心成立如果以另一个位置作中心也可能成立一个区间被反复处理逻辑上就容易乱。反过来如果中心先定下来剩下的只是向两边扩展每个子数组只会被它的唯一中心处理一次天然避免了重复。所以这类题的正向思路是别从区间出发从中心出发。把遍历的主体从“子数组”换成“中心下标k”然后再向外试探左右边界。这个思路的普适性很强很多所谓“统计满足某某条件的子数组”的题只要条件是围绕某个中心成立的都可以优先尝试枚举中心。2.2 固定中心之后指针怎么走固定中心k之后问题就变成从k出发向左扩展一步向右扩展一步每次比较左右两段的和。这里我推荐用两个滚动变量维护左右和而不是每次都重新求和。具体来说初始时左右指针分别指向k-1和k1左右和都是0。每扩展一轮就把nums[l]累加到leftSum把nums[r]累加到rightSum然后比较这两个和。如果相等答案加一。接着继续向两边扩展直到左指针越界或右指针越界。这个过程的优点是空间占用只有O(1)不需要额外数组。缺点是每个中心可能要扩展O(n)次所以总复杂度是O(n²)。但在周赛Q2的常见数据范围里这个复杂度恰恰就是正解。后面我会仔细算一笔账看O(n²)在这个题里到底能不能过。这里还有一个细节由于每轮都同时扩展左右两边所以子数组的长度一定是奇数。想清楚这一点后代码里甚至不需要显式判断长度奇偶扩展循环天然保证了这一点。2.3 相等也不能提前停这是最大的坑我在第1节里已经预告了这个坑。很多第一次做这道题的人包括我都容易在判断到leftSum rightSum之后顺手写一个break认为这一层满足条件就可以收工了。这在回文计数里通常是对的因为回文要求逐位相等一旦不等就不可能再相等但这里是区间和情况完全不同。看这个例子nums [1, 2, 3, 2, 1]中心k2向外扩一层左和是2右和是2第一次相等。继续向外扩一层左和变成123右和变成213仍然相等。如果第一层相等就break第二层就被漏掉了答案直接少1。这种“连续多层都相等”的情况在数组元素和比较随机会出现的概率并不低尤其是元素值包含0或者正负抵消时。实际上一旦左右和相等后继续扩展你仍然有可能再次相等因为新增的左右两个元素对和的贡献可能恰好相同也可能不相等那这一层不计入答案但也绝不能回头。所以循环条件只有一个只要左右指针还在数组范围内就一直扩下去。相等就记录不相等就跳过全部处理完再退出循环。这是本题实现上的核心心得。3. 参考实现与复杂度分析3.1 Python解题代码下面是我在赛场上最终提交的版本思路就是枚举中心向外扩展。代码不长但每一步都对应前面说的几个要点。class Solution: def countCenteredSubarrays(self, nums: List[int]) - int: n len(nums) ans 0 for k in range(n): # 长度为1的子数组左右都为空恒成立 ans 1 l, r k - 1, k 1 left_sum 0 right_sum 0 while l 0 and r n: left_sum nums[l] right_sum nums[r] if left_sum right_sum: ans 1 l - 1 r 1 return ans这个代码有几点值得解释。第一ans初始加1是在处理单个元素子数组而不是把k遍历时额外判断这比写一堆if要清晰。第二left_sum和right_sum是在循环内累加的天然就是当前k对应的左段和右段的和不需要每次重新算。第三while循环里无论当前层是否相等都要继续移动指针直到数组边界这避免了漏算。空间上只用了几个整数变量属于真正的O(1)额外空间。时间上最外层遍历n个中心每个中心最多扩展约n/2次所以是O(n²)。如果你担心大数相加溢出Python的int没有任何问题如果用C或Java记得开long long因为两边元素和可能超出int范围。3.2 复杂度如何计算现场怎么判断是否可行看到O(n²)有人会本能觉得不够优。但竞赛里没有绝对的最优只有题目约束下的可行。判断可行性的方法很简单看数据范围。如果题目给出n 10^4那么O(n²)最坏是10^8量级的循环加上每层只有几次加法比较C和Java在1秒内能过Python在优化较好的情况下也能过如果用PyPy更稳。如果n给到5×10^4O(n²)就是2.5×10^9这就基本没戏了必须找更优的做法。不过从周赛Q2的常见分布来看中心扩展O(n²)往往就是正解方案之一因为第二题通常不会直接考一个需要高级数据结构才能过的算法。拿到题先花30秒看一下n的规模再决定写什么这个习惯比多背几个模板都管用。我个人在现场的判断标准是如果总操作量在5×10^7到10^8之间就可以直接写如果超过5×10^8先停下来想想有没有更聪明的办法。这个数字再配合语言常数基本能预测一个解法的命运。3.3 如果中心允许元素间隙怎么扩展有读者可能会问如果题目把中心定义放宽允许中心落在两个元素之间的“间隙”上那偶数长度的子数组要不要统计这个问题看起来很合理因为部分“中心扩展”类的题目都同时处理两种中心。好在改造成本极低。元素中心的代码是左右指针从k-1和k1出发间隙中心则把左右指针从k和k1出发初始左右和都是0。也就是把数组当成“元素与元素的间隙也有资格当中轴”来对待。判断逻辑完全不变只是每一轮扩展多了一种中心来源。如果题目确实要求统计所有“中心子数组”而不仅限于以元素为中心那你就在主循环里多跑一趟间隙中心扫描。但回到这个题本身我倾向于认为题目定义的中心就是下标k不是间隙。原因很简单题名是“中心子数组”强调的是子数组本身有一个中心元素如果包含间隙中心通常会在示例里明确给出偶数长度的情况。现场不确定时可以用第二个示例反推一般就能判断清楚。4. 这类题的隐藏考点让和的单调性失效的负数4.1 负数为什么能干扰人的第一直觉如果你已经习惯滑动窗口、双指针这类技巧会不自觉以为“一边增长一边比较”的题目里和一定是单调变化的。但区间和没有任何单调性可言因为它累加的元素是可正可负的。负数的出现会让leftSum或rightSum忽大忽小前面的相等不代表后面永远相等前面的不相等更不代表后面永远不相等。这一点从题目条件就能推出来如果数组元素全为非负数那么扩展到相等后继续扩展倒是大概率会变得不相等提前break在多数情况下碰巧能过几个测试点但仍然是错的因为即便全是非负数也可能出现像[1,2,3,2,1]这种连续两层相等的情况。一旦数组里有负数错误率会成倍上升。所以负数是这道题最好的“防无脑break机制”。4.2 带负数的裂心样例看一个负数把直觉击碎的样例。nums [0, 1, -1, 0]这个数组很短但足够说明问题。手动数一下所有长度为1的子数组都成立共4个。子数组[0,2]也就是[0,1,-1]中心1左段[0]和0右段[-1]和-1不等。子数组[1,3]也就是[1,-1,0]中心2左段[1]和1右段[0]和0不等。子数组[0,3]也就是[0,1,-1,0]长度4没有整数中心下标不参与。所以答案是4。如果尝试提前break反而不会有问题但要验证的地方在于负数让leftSum和rightSum经常出现“这层不等、再扩一层反而相等”的缠绕情况。这种样例就是用来卡那些把问题想得过于简单的人。4.3 一段现场调试实录我在周赛时第一次提交就挂在了负数样例上。当时的错误代码长这样if left_sum right_sum: ans 1 break结果返回的答案明显偏小。我一开始还以为是break只影响当前中心后来构造了[1,2,3,2,1]这个例子才发现同中心下两层都相等break直接把后面的答案吞了。删掉break之后又遇到一个新的疑惑扩大范围之后leftSum和rightSum可能又变小这个现象在只有正数时根本不会出现我当时还怀疑是不是累加顺序写错。排查方法很简单我把自己当成一台“人工计算机”在草稿纸上把每个中心对应的leftSum和rightSum逐层列出来。也就是从中心向外画一个两层表格记录每一步的左右和。只要表格对得上代码逻辑就是对的对不上那就是指针移动或累加方式有问题。这个调试方法比打断点快很多尤其适合区间和类问题。5. 周赛实战心得与其他问题的迁移5.1 Q2的时间分配和策略周赛一共四题Q2往往是很多人能否稳定三题的关键分水岭。我的习惯是第一题如果三分钟内没有一次通过马上放掉继续做Q2如果Q2在15分钟内没有思路也先放掉去扫一眼Q3但这里有一个保留条件像这种“中心子数组”题核心思路几乎在标题里就暴露了。唯一需要确认的就是中心判定方式。拿到题我一般会先干三件事第一圈出“中心”前后的限定语判断是元素和相等还是值对称第二看数据范围预估复杂度第三动手写一个n5的临时数组手算答案。这三步做完Q2的撰写思路基本就清晰了。遇到这种题千万不要先想有没有O(n log n)的高级解法先把能不能枚举中心、能不能中心扩展这个问题想清楚多数Q2的正确答案就是这么朴素。5.2 同一个模式还能解决哪些问题中心扩展区间和判断这个组合在LeetCode上有一批近亲题。最典型的是回文子串计数区别是那里的扩展比较的是对应元素是否相等还有找最长有效括号、按中心统计山脉数组这类变种。它们的共同点都是“枚举可能成为中心的位置然后向外扩展判断条件”。如果某个题的条件是“以某个下标为中心左右两边各自满足某个性质”那大概率都能用这个模式套。真正需要思考的是性质是什么以及这个性质在扩展时是否增量可维护。增量可维护就用双变量累加不能增量维护就得配合前缀和或哈希表。我在另一道题里写过配合哈希表的版本先固定中心把一侧的所有可能和放进哈希表再扫描另一侧。那种做法能把某个环节的复杂度降下来但整体往往还是O(n²)只是常数更小。把中心扩展这个基本功练扎实它的价值不止于这一道3804。以后遇到任何带“中心”“对称”“中轴”关键词的题你都会先想到它再根据具体条件做微调。这个思考路径才是刷周赛真正的收获。