子序列总和 [英] Subsequence sum

问题描述

由于整数数组，例如 [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.

这篇关于子序列总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！