algorithm - 后续和

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) 执行。