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])——而不是每次都迭代。

Answer 2

为什么不只是散列增量总和并在遍历数组时更新它们的索引，获胜者是索引范围最大的那个。O(n)时间复杂度（假设平均哈希表复杂度）。

       [2, 3, -3, 4, -4, 5, 6, -6, -5, 10]
sum  0  2  5   2  6   2  7  13  7   2  12

The winner is 2, indexed 1 to 8!

为了还保证输出数组中每个数字的精确对应连续子数组，我还没有看到检查/散列候选子数组中所有和子序列的方法，这会将时间复杂度提高到O(n^2).

Answer 3

这是您要解决的问题吗？

给定一个序列，找到最大化使得

如果是这样，这是解决它的算法：

let $U$ be a set of contiguous integers
for each contiguous $S\in\Bbb Z^+_{\le n}$
    for each $\T in \wp\left([i,j)\right)$
      if $\sum_{n\in T}a_n = 0$
        if $\left|S\right| < \left|U\left$
          $S \to u$

返回 $U$

（一旦有机会，将使用全乳胶进行更新。）

Answer 4

基于这个例子，我假设你只想找到两个值加起来等于 0 的值，如果你想包括那些加起来等于 0 的值（比如 5 + -2 + - 3），那么您需要进一步澄清您的参数。

实现因语言而异，但这里有一个显示算法的 javascript 示例，您可以用任何语言实现该算法：

var inputArray = [2, 3, -3, 4, -4, 5, 6, -6, -5, 10];
var ouputArray = [];

for (var i=0;i<inputArray.length;i++){
    var num1 = inputArray[i];

    for (var x=0;x<inputArray.length;x++){
        var num2 = inputArray[x];
        var sumVal = num1+num2;
        if (sumVal == 0){
            outputArray.push(num1);
            outputArray.push(num2);

        }

    }
}