arrays - 查找数组中总和为零的所有数字

Question

给定一个数组，输出数组中总和为0的连续元素。

例如:

对于输入 [2, 3, -3, 4, -4, 5, 6, -6, -5, 10],

输出为 [3, -3, 4, -4, 5, 6, -6, -5]

我找不到最佳解决方案。

说明1:对于输出子数组中的任何元素，子数组中应该有一个子集，它与元素相加为零。

例如:对于 -5，应该存在 子集 {[-2, -3], [-1, -4], [-5], ....}在输出子数组中。

说明2:输出子数组应该是所有连续的元素。

Answer 1

这是一个在 O(n³) 中运行的 python 解决方案:

def conSumZero(input):
    take = [False] * len(input)

    for i in range(len(input)):
        for j in range(i+1, len(input)):
            if sum(input[i:j]) == 0:
                for k in range(i, j):
                    take[k] = True;

    return numpy.where(take, input)

编辑:现在更有效率了! (不确定它是否完全是 O(n²)；一旦我计算完复杂性就会更新。)

def conSumZero(input):
    take = [False] * len(input)
    cs = numpy.cumsum(input)
    cs.insert(0,0)

    for i in range(len(input)):
        for j in range(i+1, len(input)):
            if cs[j] - cs[i] == 0:
                for k in range(i, j):
                    take[k] = True;

    return numpy.where(take, input)

这里的区别在于我预先计算了序列的部分和，并使用它们来计算子序列和 - 因为 sum(a[i:j]) = sum(a[0:j]) - sum (a[0:i]) - 而不是每次都迭代。