🎮 村长云服务器危机：从暴力枚举到哈希增量的三重奏
“小白！我搞了台二手服务器！” 今天一大早，村长抱着一个嗡嗡作响的铁盒子冲进来，机箱风扇发出拖拉机般的轰鸣声。机箱上贴着歪歪扭扭的标签——村长云服务器·内测版，旁边还画了一个丑萌丑萌的云朵图案。
他把显示器往桌上一搁，屏幕上是一条不断刷新的日志流，每行要么是绿色的"SUCCESS"，要么是红色的 “FAIL”，密密麻麻地滚动着，像黑客帝国里的代码雨。
“你看这个监控系统，”村长指着屏幕，自豪中带着几分心虚，“它每秒记录一次请求状态——成功或者失败。小卖部老板娘把她的抽奖系统挂在我这台服务器上了，结果运行了三天，抽奖页面崩了五回！”
他压低声音，神色紧张：“老板娘说如果再崩，她就换隔壁村老李的服务器。我得找出所有出问题的时间段，证明我的服务器只是‘短暂波动’，不是‘性能不行’！”
我凑近一看，日志已经跑了好几千条，密密麻麻的绿色和红色交替闪烁，像一棵圣诞树。村长调出一个运维面板，上面写着故障判定规则：
如果一段连续时间内，失败请求的次数超过总请求数的一半，这段区间就是“故障窗口”。
“也就是说，我需要统计所有可能的故障窗口，看看哪些时间段服务器最脆弱——” 村长搓着手，一脸殷勤地看着我，“小白，你不是最擅长统计什么‘子数组个数’吗？帮我算算？算完了我给你充一百块服务器体验券！”
我盯着屏幕上的日志流：“这不就是把 FAIL 当成 target，SUCCESS 当成其他元素，找所有 target 出现次数超过一半的子数组吗——" 于是，我拍拍胸脯，自信地说：”村长，没问题！净胜球统计，FAIL +1，SUCCESS -1，净胜球大于 0 就是故障窗口。先上暴力跑通逻辑！“
第一幕·暴力初探
双重循环枚举所有可能的连续时间段（也就是所有子数组）。外层循环定起点，内层循环往后扩展，同时维护一个净胜球计数器cnt——遇到target就+1，遇到非target就-1。cnt大于0的瞬间，说明从起点到当前位置这段区间里，target的出场次数已经压过了其他元素，故障窗口成立，答案加一。
def countMajoritySubarrays(nums: List[int], target: int) -> int:
n = len(nums)
ans = 0
for i in range(n): # 枚举子数组的起始位置
cnt = 0 # target 相对于其他元素的净胜球
for j in range(i, n): # 枚举子数组的结束位置
cnt += 1 if nums[j] == target else -1 # 如果是target，+1；否则-1
if cnt > 0: # 如果target的净胜球大于0，说明它是主要元素
ans += 1 # 计数器加1
return ans
跑了一遍样例——完美。我正准备提交，瞥见村长的服务器日志已经跑到了好几千条，红色的 FAIL 和绿色的 SUCCESS 还在屏幕上疯狂滚动。“村长，您这日志数据量多大？”我问道。
“不多不多，目前才几千条，”村长摆摆手，一脸轻松，“不过老板娘说抽奖活动要持续一年！每天都有新日志！到时候我这’村长云’的数据量可是海量的！”
我心里暗暗叫苦——几千条用 O(n²) 还能扛住，但一年下来怕是能积累到十万条甚至更多——那时候就是上百亿次操作了。O(n²) 的暴力法绝对会炸，连渣都不剩。
“不行，我得提前想好优化方案。”我盯着代码里那个 cnt 变量，陷入了沉思。
第二幕·前缀和+SortedList
暴力法的瓶颈很明显：对于每一个起点i，暴力法都要从i出发一步一步往右走，边加边判——相邻两个起点 i 和 i+1 之间，大量中间计算结果被白白扔掉了。明明[i, j]和[i+1, j]的净胜球只差nums[i]这一个元素的贡献，但暴力法把整段重新算了一遍。重复计算，O(n²)的万恶之源。
如果能用什么东西把“从开头到某个位置”的净胜球存下来，那任意区间[i, j]的净胜球就变成了两个值的减法。等等——这不就是前缀和吗！
我在草稿纸上快速推导：
定义 prefix[k] 为前 k 条记录的净胜球，prefix[0] = 0，表示还没开始时的空状态。
对于任意区间 (i, j]，它的净胜球就是 prefix[j] - prefix[i]。
要让它成为故障窗口，需要 prefix[j] - prefix[i] > 0，
移项得：prefix[j] > prefix[i]
“对于每个位置 j，我不再需要枚举所有可能的起点 i，而是只需要统计前面有多少个位置的前缀和小于 prefix[j]！”
原本要枚举所有子数组的问题，现在变成了一个动态查询问题——随着遍历的进行，不断维护一个历史前缀和的集合，并快速查询“有多少个历史值小于当前值”。
用什么数据结构存前缀和来支持快速查询呢？我在脑子里飞快地过了一遍：普通数组？查询需要遍历，O(n)，pass。排序数组？插入需要移动元素，还是 O(n)，pass。平衡二叉搜索树——插入和查询都是 O(log n)，完美！Python 标准库里虽然没有平衡树，但 sortedcontainers 里的 SortedList 就是这个角色的天选之子——内部维护有序列表，支持 O(log n) 的二分查找和插入，简直是给这道题量身定做的！
思路瞬间清晰起来：
- 初始化一个 SortedList，放入初始前缀和 0（对应prefix[0]，表示还没开始时的状态）
- 遍历数组，维护当前前缀和 s：如果当前元素是 target，前缀和 +1；否则 -1
- 对于每个位置，用
bisect_left(s)查询有多少个历史前缀和小于 s，累加到答案中 - 将当前前缀和 s 加入 SortedList，供后续位置查询。
from sortedcontainers import SortedList
def countMajoritySubarrays(nums: List[int], target: int) -> int:
sl = SortedList([0]) # 初始化前缀和有序列表，包含哨兵0
ans = s = 0 # ans是答案，s是当前前缀和
for x in nums:
s += 1 if x == target else -1 # 更新前缀和
ans += sl.bisect_left(s) # 查找小于s的前缀和个数
sl.add(s) # 将当前前缀和加入有序列表
return ans
提交，AC弹出来的速度比服务器日志刷新还快。暴力到有序，时间复杂度就从 O(n²) 降到了 O(n log n)！就算日志增长到十万条，也能在合理时间内算完！
村长看着运维面板上标注出来的故障窗口，乐得合不拢嘴：“这些时间段的故障窗口果然集中在下半夜！我就说下半夜没人值班，服务器自己跑着跑着就崩了！看老板娘还怎么怪我的二手服务器不行！”
“数据结构的力量！” 我得意地晃了晃鼠标，“能用 O(n log n) 绝不用 O(n²)，能秀操作绝不写普通代码。村长，您这二手服务器配上我这优化算法，就是生产级稳定性——” 话还没说完，后脑勺挨了精准的一下。
第三幕·哈希表 + 动态维护
“SortedList 都掏出来了，有长进。”老勇者扫了眼屏幕上那段 SortedList 代码，嘴角微微上扬。
“O(n log n) 能过，”他话锋一转，“但你这还是在用有序结构做查找。SortedList 内部维护了一棵红黑树，每次插入和查询都要在树里走一圈，常数因子不小。”
我愣了一下：“什么意思？这可是 O(n log n) 的高效算法啊！”
老勇者拿过笔，在纸上画了一条上下波动的折线，“你仔细看，你这前缀和 s 每次怎么变的？”
“遇到 target 加一，遇到非 target 减一。步子很小，每次只变 ±1。”
“这就是关键——步子很小。”老勇者用笔尖在折线上点了点，“你想过没有，既然 s 每次只变化 1，那’有多少个历史前缀和小于 s’这个数量，是不是也不需要每次都重新计算？”
我皱起眉头：“不重新计算？s 变了之后，符合条件的历史位置会变啊……”
“没错，但它们的变化是有规律的。”老勇者眼中闪过一丝狡黠，“如果你维护一个变量 f，表示’以当前位置为右端点时，满足 prefix[i] < s的左端点个数’。当 s 变化时，f 不需要从头算——它只需要做一次增量更新。”
我若有所思：“增量更新？每次加多少，减多少？”
“看 s 怎么变。”老勇者在纸上写下递推关系，“如果当前元素是 target，s 会增加 1，变成 new_s = s + 1 。原来那些 前缀和 < s 的 i 依然满足条件。此外，那些前缀和恰好等于s 的 i ，现在也满足条件了——因为 s < new_s 。”
他停顿了一下，盯着我问：“所以，f 应该增加多少？”
我脑子飞速运转：“应该增加……那些 前缀和恰好等于 s 的历史位置个数？”
“正是！”老勇者满意地点头，“如果我们用一个哈希表 cnt 来记录每个前缀和出现的次数，那么 cnt[s] 就是前缀和恰好等于 s 的历史位置个数。所以当 s 增加 1 时，f 应该增加 cnt[s]。”
老勇者又把笔尖折向下方：“反过来，如果当前元素不是 target，s 会减少 1，变成 new_s = s - 1。原来那些前缀和< s 的历史位置中，那些前缀和恰好等于 new_s（也就是 s - 1）的位置，现在不再满足条件了——因为现在要求的是小于 new_s，而它们等于 new_s，不满足’严格小于’。”
他抬起头，眼神锐利：“所以，f 应该减去多少？”
我恍然大悟：“应该减去那些 前缀和恰好等于 new_s 的历史位置个数，也就是 cnt[s - 1]！”
“没错！”老勇者露出欣慰的笑容，“通过这种方式，每次只需要 O(1) 的时间就能更新 f，连二分查找都省了！”
def countMajoritySubarrays(nums: List[int], target: int) -> int:
cnt = defaultdict(int)
cnt[0] = 1 # 初始前缀和0出现一次（哨兵）
ans = s = f = 0
for x in nums:
if x == target:
f += cnt[s] # 新增那些前缀和恰好等于当前s的起始位置
s += 1
else:
s -= 1
f -= cnt[s] # 减去那些前缀和恰好等于新s的起始位置（不再满足条件）
ans += f # 累加当前位置的贡献
cnt[s] += 1 # 将当前前缀和加入哈希表
return ans
提交，AC 弹出来的速度比村长那台二手服务器的风扇还快——O(n) 空间，O(n) 时间！
“每次更新f只需要O(1)，然后把f累加到答案，再把新的s加入哈希表。”我激动地指着屏幕，“一趟遍历，没有任何嵌套循环，也没有任何二分查找！纯纯的O(n)！从O(n²)暴力到O(n log n)有序集合，再到O(n)哈希表——这优化曲线比过山车还刺激！”
老勇者点了点头：“步长±1这个性质，让你不用再问‘有多少个小于s’，只需要在s变化的时候把答案顺手更新一下。SortedList是通用解，哈希表+变量f是特化解——知道什么时候该通用，什么时候该特化，这趟副本才算没白刷。”
尾声
村长抱着服务器乐颠颠地回去找老板娘邀功了，跑出去老远还能听见他在喊：“小白！老板娘说抽奖活动可能要搞三年，日志量会爆炸——你那O(n)扛得住吗？”
我靠在椅背上，总觉得这句式有点耳熟——上次村长说‘这个需求很简单’，隔天就甩过来一个‘锯齿过山车 II’。这次直接喊三年，怕不又是‘村长云监控 II’的预告，那种在数据量后面加好几个零的加强版。
“扛得住！”我扯着嗓子回了一句，“三年日志算什么，三十年也照跑不误！O(n)的意思就是日志翻倍，时间只翻倍——除非老板娘把抽奖活动搞到太阳系毁灭，不然我这算法稳如老狗！”
我把三版代码并排收进魔法书，在旁边补了几句：
**暴力枚举探本质，前缀和转区间查。 ** SortedList虽快非极致，哈希增量最潇洒。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。