找到总和为零的连续子阵列的数量

Question

你已经给出了一个数组,你必须给出连续子数的数量,其总和为零.

example:
1)  0 ,1,-1,0 => 6 {{0},{1,-1},{0,1,-1},{1,-1,0},{0}};
2)  5, 2, -2, 5 ,-5, 9 => 3.

使用O(n ^ 2)就可以完成.我正在尝试找到低于这种复杂性的解决方案.

Answer 1

考虑S [0..N] - 数组的前缀和,即S [k] = A [0] + A [1] + ... + A [k-1],k从0到N.

现在,当且仅当S [R] = S [L]时,从L到R-1的元素之和为零.这意味着你必须找到索引数0 <= L <R <= N,使得S [L] = S [R].

使用哈希表可以解决此问题.迭代S []的元素,同时为S []的已处理部分中的每个值保持X次.这些计数应存储在哈希映射中,其中数字X是键,计数H [X]是值.当你遇到一个新元素S [i]时,在你的答案中添加H [S [i]](这些用于以(i-1)-st元素结尾的子串),然后将H [S [i]]加1 .

请注意,如果数组元素的绝对值之和很小,则可以使用简单数组而不是哈希表.复杂性平均线性.

这是代码:

long long CountZeroSubstrings(vector<int> A) {
    int n = A.size();

    vector<long long> S(n+1, 0);
    for (int i = 0; i < n; i++)
        S[i+1] = S[i] + A[i];

    long long answer = 0;
    unordered_map<long long, int> H;
    for (int i = 0; i <= n; i++) {
        if (H.count(S[i]))
            answer += H[S[i]];
        H[S[i]]++;      
    }

    return answer;
}

Answer 2

我不知道我的建议的复杂性是什么，但我有一个想法:)
你可以做的是尝试减少主数组中的元素，这些元素无法为你的解决方案做出贡献，假设元素是，-10, 5, 2, -2, 5,7 ,-5, 9,11,19
这样你就可以看到-10,9,11 and 19它们永远不会消失的元素在您的情况下
很有用 ，因此请尝试从主数组中删除以执行此操作，您可以做的是 sum 0
-10,9,11, and 19

1) create two sub array from your main array  
`positive {5,7,2,9,11,19}` and `negative {-10,-2,-5}`   
2) remove element from positive array which does not satisfy condition
   condition -> value should be construct from negative arrays element  
   or sum of  its elements  
   ie.   
       5 = -5 //so keep it //don't consider the sign  
       7 = (-5 + -2 ) // keep  
       2 = -2 // keep
       9 // cannot be construct using -10,-2,-5  
       same for all 11 and 19
3) remove element form negative array which does not satisfy condition
      condition -> value should be construct from positive arrays element  
       or sum of  its elements   
  i.e. -10 // cannot be construct so discard  
       -2 = 2 // keep  
       -5 = 5 // keep 

所以最后你得到了一个包含 -2,-5,5,7,2 的数组，从中创建所有可能的子数组并检查 sum = 0
（注意，如果你的输入数组包含 0，则在最终数组中添加所有 0）