子序列总和

本文介绍了子序列总和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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