生成子数组和为零的数组的算法

Question

我想随机生成一个整数数组，范围在-10^7到10^7之间，并且这个数组里要有一个子数组的和为零。

比如说：7 6 4 8 -4 -8

数组的大小要在1到10^5之间。

我现在是用暴力破解的方法来实现，但这样做耗时太长，因为我需要生成非常大的数组。有没有什么更高效的方法可以用Python或C++来实现呢？

补充一下：其实我想生成很多这样的数组，场景各不相同。我生成这些数组是为了测试一个问题，看看给定的正负整数数组中是否包含和为零的子数组。

我尝试过的暴力破解代码：

import random
N = random.randint(10,100)
mylist = []
for i in xrange(1,N):
  mylist.append(random.randint(-100,100))
list2 = [1,-1]
mylist = mylist[1:N-2] + list2 + mylist[N-2:N]
print mylist

所以我得手动调整很多地方。

谢谢！

Answer 1

这个答案取决于你想让你的数组有多“随机”。就像一些评论者提到的，你可以总是包含一个零，这样就能确保有一个子数组的和为零。我觉得这对你最终的解决方案会有帮助，所以我想提一下，你可以在O(N^2)的时间内检查一个数组是否有和为零的子数组。

def array_has_zerosubarray( A ):
    for _begin in xrange(0,len(A)-1):
       for _end in xrange(_begin+1,len(A)):
           sum = 0
           for ai in range(_begin,_end):
               sum = sum + A[ai]
           if sum==0:
              return True
    return False