计数给定和为零的所有相邻子数组

Question

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)？

Answer 1

设数组为a1，…，an。设s0，...，sn是由sj=a1+...+aj（和s0=0)定义的前缀和。从i到j的子数组之和是sj-si-1。对于O(n)/O(n，log，n)-time算法，使用映射计算前缀和中每个数字的出现次数。求和k，在这个映射的值中选择2作为k。

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

1 -1 2 -2 6 -6

则前缀和为

0 1 0 2 0 6 0

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

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())