问题描述
由于整数数组，例如 [1，2，-3,1] 查找是否有一个子序列，总结为 0 并返回它（例如： [1，2，-3] 或 [2，-3,1] ）。
检查每个子序列为O（n ^ 2）这是效率太低。任何想法改善？
Given an array of integers eg [1, 2, -3, 1] find whether there is a sub-sequence that sums to 0 and return it (eg [1, 2, -3] or [2, -3, 1]).
Checking every sub-sequence is O(n^2) which is too inefficient. Any idea for improvements?
推荐答案
请一个新的数组，每个元素等于previous元素加一个总和。
Make a new array with each element equal to the sum of the previous elements plus that one.
输入：
1 4 -3 -4 6 -7 8 -5
变成了：
1 5 2 -2 4 -3 5 0
^ ^
然后寻找匹配所得数组中的元素。
Then look for elements that match in the resulting array.
由于这些重present位置，其中在功能上的整体变化是零，你会发现，如果他们的立场是I和K则子（I + 1，k）是一个零和子序列。 （在这种情况下，[2：6]）。
Since these represent locations where the overall change in the function is zero, you will find that if their position is i and k then the subsequence (i+1, k) is a zero-sum subsequence. (In this case, [2:6]).
此外，表中的任意零指示的序列（0，k）是一个零和子序列。对于查找，哈希表或其它快速碰撞定位使得这款O（N）来执行。
Additionally, any zeros in the table indicate that the subsequence (0, k) is a zero-sum subsequence. For the lookup, a hash table or other fast collision locator makes this O(N) to perform.
这篇关于子序列总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！