给定总和为零的所有连续子数组 [英] Counting all contiguous sub-arrays given sum zero

问题描述

给定长度为n的随机数（正数和负数）数组，我想要数字连续的子数组，其总和等于零。

Given array of random numbers(positive, and negative) with length n, I want number contiguous sub-arrays which sum equals zero.

示例：
鉴于我有数组 a = {1，-1，2，-2 ，6，-6} ，输出将为 6 ，因为子数组如下：

Example: Given I have array a={1, -1 ,2 , -2, 6, -6}, output will be 6 because sub-arrays are as the following:

1 -1 & 2 -2 & 6 -6 & 1 -1 2 -2 & 2 -2 6 -6 & 1 -1 2 -2 6 -6

我知道蛮力解O（n ^ 2），我想要其他解决方案O（n）或O（n log n）吗？

I know brute force solution O(n^2), I want any another solution O(n), or O(n log n) ?

推荐答案

让数组为a1，。 ..，一个令s0，...，sn为sj = a1 + ... + aj（和s0 = 0）定义的前缀和。从i到j的子数组之和为sj-si-1。对于O（n）/ O（n log n）时间算法，使用映射，计算前缀总和中每个数字的出现次数。总和k在此地图的值中为k选择2。

Let the array be a1, ..., an. Let s0, ..., sn be the prefix sums defined by sj = a1 + ... + aj (and s0 = 0). The sum of the subarray from i to j inclusive is sj - si-1. For an O(n)/O(n log n)-time algorithm, using a map, count the number of occurrences of each number among the prefix sums. Sum k choose 2 for k in the values of this map.

例如，如果我们有您的数组

For example, if we have your array

1 -1 2 -2 6 -6

然后前缀总和是

0 1 0 2 0 6 0

，计数为

0: 4
1: 1
2: 1
3: 1

，输出为4选择2 + 1选择2 + 1选择2 + 1选择2 = 6（其中k选择2 = k（k-1）/ 2）。

and the output is 4 choose 2 + 1 choose 2 + 1 choose 2 + 1 choose 2 = 6 (where k choose 2 = k(k-1)/2).

在Python中：

def countsumzero(lst):
    prefixsums = [0]
    for x in lst:
        prefixsums.append(prefixsums[-1] + x)
    freq = {}
    for y in prefixsums:
        if y in freq:
            freq[y] += 1
        else:
            freq[y] = 1
    return sum(v*(v-1) // 2 for v in freq.values())

这篇关于给定总和为零的所有连续子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！