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

问题描述

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

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

08-21 03:39