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）：

#!/usr/bin/env python

import sys 

def find_zero_sum_seq(seq):
  sums = [0] * len(seq)
  for i, x in enumerate(seq):
    for j in range(0, i + 1): 
      sums[j] += seq[i]
      if sums[j] == 0:
        return (j, i)
    print ‘debug’, sums
   
if __name__ == ‘__main__’:
  seq = [int(x) for x in sys.argv[1:]]
  print find_zero_sum_seq(seq) or ‘not found’

#!/usr/bin/env python

import sys

def find_zero_sum_seq(seq):

sums = [0] * len(seq)

for i, x in enumerate(seq):

for j in range(0, i + 1):

sums[j] += seq[i]

if sums[j] == 0:

return (j, i)

print ‘debug’, sums

if __name__ == ‘__main__’:

seq = [int(x) for x in sys.argv[1:]]

print find_zero_sum_seq(seq) or ‘not found’

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

$ python zero-sum.py 4 1 1 1 1 2 4 -1 -6 10
debug [4, 0, 0, 0, 0, 0, 0, 0, 0, 0]
debug [5, 1, 0, 0, 0, 0, 0, 0, 0, 0]
debug [6, 2, 1, 0, 0, 0, 0, 0, 0, 0]
debug [7, 3, 2, 1, 0, 0, 0, 0, 0, 0]
debug [8, 4, 3, 2, 1, 0, 0, 0, 0, 0]
debug [10, 6, 5, 4, 3, 2, 0, 0, 0, 0]
debug [14, 10, 9, 8, 7, 6, 4, 0, 0, 0]
debug [13, 9, 8, 7, 6, 5, 3, -1, 0, 0]
(4, 8)
$ python zero-sum.py 1 2 -1 8 -9
debug [1, 0, 0, 0, 0]
debug [3, 2, 0, 0, 0]
debug [2, 1, -1, 0, 0]
debug [10, 9, 7, 8, 0]
(1, 4)

$ python zero–sum.py 4 1 1 1 1 2 4 –1 –6 10

debug [4, 0, 0, 0, 0, 0, 0, 0, 0, 0]

debug [5, 1, 0, 0, 0, 0, 0, 0, 0, 0]

debug [6, 2, 1, 0, 0, 0, 0, 0, 0, 0]

debug [7, 3, 2, 1, 0, 0, 0, 0, 0, 0]

debug [8, 4, 3, 2, 1, 0, 0, 0, 0, 0]

debug [10, 6, 5, 4, 3, 2, 0, 0, 0, 0]

debug [14, 10, 9, 8, 7, 6, 4, 0, 0, 0]

debug [13, 9, 8, 7, 6, 5, 3, –1, 0, 0]

(4, 8)

$ python zero–sum.py 1 2 –1 8 –9

debug [1, 0, 0, 0, 0]

debug [3, 2, 0, 0, 0]

debug [2, 1, –1, 0, 0]

debug [10, 9, 7, 8, 0]

(1, 4)

箱猫日和

zero sum subsequence problem solution 1

One response to “zero sum subsequence problem solution 1”