给定一个长度为n的随机数数组(包括正数和负数),我想要找到相加等于零的子数组个数。
示例:
给定数组a={1, -1 ,2 , -2, 6, -6}
,输出结果应为6
,因为子数组如下:
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)的解决方案,你能帮忙提供吗?
给定一个长度为n的随机数数组(包括正数和负数),我想要找到相加等于零的子数组个数。
示例:
给定数组a={1, -1 ,2 , -2, 6, -6}
,输出结果应为6
,因为子数组如下:
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)的解决方案,你能帮忙提供吗?
设数组为a1,...,an。令s0,...,sn是由sj = a1 + ... + aj(其中s0 = 0)定义的前缀和。从i到j(包括i和j)的子数组之和是sj - si-1。使用映射实现O(n)/O(n log n)时间复杂度算法,计算每个前缀和中每个数字出现的次数。对于该映射中的值k,计算k个选择2的和。
例如,如果我们有以下数组
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)。
在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())