统计包含和为零子段的数组区间数量

你的思路方向是对的，但直接遍历所有区间统计会导致O(N²)的时间复杂度，我们可以通过补集思想优化：计算总区间数减去完全不包含任何和为零子段的区间数，能把时间复杂度降到O(N)。

核心思路 #

1. 总区间数固定：长度为N的数组，总区间数为 total = N * (N + 1) // 2。
2. 不合法区间的判定：完全不包含和为零子段的区间，等价于该区间对应的前缀和子数组中所有元素唯一——因为若前缀和出现重复，说明这两个位置之间的子段和为零。
3. 滑动窗口统计不合法区间：用双指针维护一个窗口，保证窗口内的前缀和唯一。对每个右指针位置，计算以当前右边界对应的数组位置为结尾的不合法区间数量，累加得到总不合法区间数。

具体步骤 #

1. 前缀和定义：设s[0] = 0，s[i] = s[i-1] + nums[i-1]（i从1到N）。子段nums[a..b]的和为s[b+1] - s[a]，和为零当且仅当s[b+1] = s[a]。
2. 滑动窗口遍历：
   • 用哈希表记录每个前缀和最近出现的索引。
   • 维护左指针left，确保s[left..right]内元素唯一。若当前前缀和s[right]已在窗口内出现过，将left移动到该前缀和上次出现位置的下一位。
   • 每个right对应的不合法区间数为right - left（即左边界从left到right-1的区间），累加到invalid中。
3. 计算最终答案：answer = total - invalid。

代码实现（Python） #

def count_zero_subarray_containing_intervals(nums):
    n = len(nums)
    total = n * (n + 1) // 2
    prefix_sum = 0
    last_occurrence = {0: 0}
    left = 0
    invalid = 0
    
    for right in range(1, n + 1):
        prefix_sum += nums[right - 1]
        # 若当前前缀和在窗口内重复，移动左边界
        if prefix_sum in last_occurrence and last_occurrence[prefix_sum] >= left:
            left = last_occurrence[prefix_sum] + 1
        # 更新当前前缀和的最新位置
        last_occurrence[prefix_sum] = right
        # 累加不合法区间数
        invalid += right - left
    
    return total - invalid

示例验证 #

• 数组[5, -5, 5]：总区间数6，不合法区间数3，答案6-3=3，符合预期。
• 数组[1,2,3,-6]：总区间数10，不合法区间数9，答案10-9=1，符合预期。

复杂度分析 #

• 时间复杂度：O(N)，每个元素最多被左右指针各遍历一次，哈希表操作平均为O(1)。
• 空间复杂度：O(N)，最坏情况下前缀和全不重复，哈希表存储N+1个元素。

内容的提问来源于stack exchange，提问作者annflames