查找所有數字在陣列其中薩姆高達零

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

基於這個例子，我假定你只想找到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); 

     } 

    } 
} 

Answer 2

這裏是一個運行在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]) - 而不是每次迭代。

Answer 3

爲什麼在遍歷數組的時候不僅散列增量總和並更新它們的索引，贏家就是索引範圍最大的那個。 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 4

這是你想解決的問題嗎？

給定一個序列，發現最大化這樣

如果是這樣，這裏是解決它的算法：

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 $

（一旦我有機會，請用全乳膠更新。）