后续总和

Question

给定一个整数数组,例如[1, 2, -3, 1]查找是否存在与其求和0并返回的子序列(例如[1, 2, -3]或[2, -3, 1]).
检查每个子序列的O(n^2)效率太低.有任何改进的想法吗？

Answer 1

创建一个新数组,每个元素等于前一个元素加上该元素的总和.

输入:

1  4 -3 -4  6  -7  8 -5

变为:

1  5  2  -2  4  -3  5  0
   ^                ^

然后在结果数组中查找匹配的元素.

由于这些代表函数整体变化为零的位置,您会发现如果它们的位置是i和k,则子序列(i + 1,k)是零和子序列.(在这种情况下,[2:6]).

另外,表中的任何零表示子序列(0,k)是零和子序列.对于查找,哈希表或其他快速冲突定位器使该O(N)执行.

Answer 2

执行运行总和,将和值与数组索引一起存储在哈希表中

如果你得到一个你已经看过的和值,则返回1 +哈希表中的索引和当前索引.该解决方案是O(n)时间复杂度.

不需要新阵列.由于散列,空间复杂度为O(N).

Python实现:

input = [1, 4, -3, -4, 6, -7, 8, -5]
map = {}
sum = 0
for i in range(len(input)):
    sum += input[i]
    if sum in map:
        print map[sum][0] + 1, "to", i
    map[sum] = (i, sum)

请注意,未显示重复的子序列,例如:如果(1到2)是子序列,(3到4),则不会显示(1到4).您可以通过在地图的每个位置存储列表来实现此行为:

for x in map[sum]:
    print x[0]+1, "to", i
map[sum].append((i, sum))