查找所有数字在阵列其中萨姆高达零

鉴于阵列，输出阵列的连续元素，其中总和是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：输出子阵列应该是所有连续的元素。

来源

2015-09-20 Sreejith Ramakrishnan

define ** optimal ** ...你忘了这么做。 –

另外，什么语言？ – AJMansfield

排除元素数量最少？这是否相当于取得总和，然后找到最少的元素加起来呢？ –

基于这个例子，我假定你只想找到2个值一起加起来为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); 

     } 

    } 
}

来源

2015-09-20 15:44:00 CodeMonkeyArtist

我敢肯定，你不能只期望找到+ x和-x对。您需要处理[...，2，2，-4，...] –

此解决方案不正确。如果数字对不相邻，这将重新排列顺序，并且它将输出每个数字两次。 – AJMansfield

@KennyOstrom示例包含-4。 -6和10，但没有输出10。 – AJMansfield

这里是一个运行在O蟒蛇溶液（N 3）：

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

来源

2015-09-20 16:19:44 AJMansfield

https://en.wikipedia.org/wiki/Prefix_sum是非常酷:) –

我喜欢它，但不应该开始j和结束并向后工作，所以你首先检查最大的解决方案？这样，您可以在找到解决方案时立即终止搜索。仅仅通过视觉检查，看起来您会发现所有可能的解决方案，将它们标记为“接受”，然后将它们合并在一起。但是如果两个不同的解决方案合并到一个输出中，并且合计为非零值呢？ –

对照[1，2，3，-6，1，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)。

来源

2015-09-20 21:54:27

当您计算部分总和时，您可以查看之前是否发生过部分总和，并为您提供零总和子集的开始和结束（因此为长度）。存储时间最长。你使用哈希表（dict）来断言O（1）的查找。好吧，我喜欢它。可能包含0作为第一个总和，因此您可以处理第一个条目为0的输入？ –

@KennyOstrom感谢评论。我认为我的初始金额为零。无论如何，我补充说。 –

如果输出和为0，则每个项目都有一个完全相同的输出数组的其余部分。 –

这是你想解决的问题吗？

给定一个序列 $A=a_1...a_n$ ，发现 $S=[i,j)\subseteq\Bbb Z$ 最大化 $i-j$ 这样

$\forall k\in S\;\exists\,T\subseteq S:k\in T,\sum_{m\in T}a_m=0$

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

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 $

（一旦我有机会，请用全乳胶更新。）

来源

2015-09-21 20:51:16 AJMansfield

查找所有数字在阵列其中萨姆高达零

回答

相关问题