zero sum subsequence problem solution 1


题目是这样的,给定一个整数序列,比如[1, 2, -1, 8, -9],要求找出一个子序列,其所有数字的和为0,比如子序列[2, -1, 8, -9],并输出子序列在主序列中的位置,比如[2, -1, 8, 9]在主序列[1, 2, -1, 8, -9]中的位置为[1, 4]。

以下是我想到的一个方法,暂时不清楚怎么计算这个的时间复杂度。原理是这样的,对于序列[1, 2, -1, 8, -9],设置一个和序列。初始为[0, 0, 0, 0, 0],长度和输入序列一致。
顺序读取输入序列,第一次遇到1,尝试在和序列的[0, 0]区别内增加1,结果为[1, 0, 0, 0, 0]。为什么这么做呢,这样,输入序列区间[0, 0]的和就计算出来了。
第二次遇到2, 尝试在和序列[0, 1]区间内增加2,结果为[3, 2, 0, 0, 0],这样,输入序列区间[0, 1], [1, 1]的和就计算出来了。没有发现0和序列。
接下来依此类推,发现[1, 4]区间的和为0,输出为(1, 4)。代码如下(python):

执行和输出,debug为和序列的内容。


One response to “zero sum subsequence problem solution 1”

  1. 连续子列的话先求出a[0], a[0] + a[1], …, a[0] + … + a[k], …, a[0] + … + a[n-1]这n个数,然后排序看有没有重复元素出现,O(nlgn)时间应该是最优的