Meta 连续子数组和计数：前缀频次与负数

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入可包含正、负、零，目标可为任意整数；按下标区间计数，同值的不同区间分别算。
• Python整数无固定宽度溢出；其他语言需确保前缀和与总数量能容纳n(n+1)/2。

解题路线

1. 区间[i,j)和等于target等价于prefix[j]−prefix[i]=target。扫到当前prefix时，所有此前prefix−target的出现次数都是以当前元素结尾的合法区间。
2. freq初始化{0:1}覆盖从下标0开始的区间；先查再累加当前prefix，避免target=0时把空区间算入。
3. 计数频率而不是set，重复前缀对应不同左端点；如全零数组，每步新增之前前缀数，产生三角数。

手动走一遍

[1,−1,0]、target0得到3：[1,−1]、[1,−1,0]、[0]。三个0产生6个区间；set只能知道前缀存在，无法得到正确数量。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def count_subarrays(values, target):
    frequencies = {0: 1}
    total = answer = 0
    for value in values:
        total += value
        answer += frequencies.get(total - target, 0)
        frequencies[total] = frequencies.get(total, 0) + 1
    return answer

复杂度

O(n)预期哈希时间，O(n)辅助空间；最坏哈希退化需根据语言实现讨论。

易错点与追问

容易失分的边界

• 先更新freq再查询会额外计入每个位置的空区间。
• 正数滑窗代码不能承担含负数的计数版，题面约束改变必须换解法。

继续深挖

• 若要求最长区间，保存每个前缀最早下标；最短区间则保留最近下标，输出目标决定存储信息。
• 二维matrix sum=target可固定上下边界压缩列，使用一维频次计数；复杂度O(min(R,C)² max(R,C))。