c - 优化此代码以检查总和

Question

这就是问题，我正在尝试在 SPOJ 中解决。我遇到超出时间限制的问题。我找不到优化算法的方法。你能给我一些建议吗？

问题是这样的:

Leonard had to find the number of continuous sequence of numbers such that their sum is zero.

For example if the sequence is- 5, 2, -2, 5, -5, 9

There are 3 such sequences

2, -2

5, -5

2, -2, 5, -5

Since this is a golden opportunity for Leonard to rewrite the Roommate Agreement and get rid of Sheldon's ridiculous clauses, he can't afford to lose. So he turns to you for help. Don't let him down.

Input

First line contains T - number of test cases

Second line contains n - the number of elements in a particular test case.

Next line contain n elements, ai (1<=i<= n) separated by spaces.

Output

The number of such sequences whose sum if zero.

Constraints

1<=t<=5

1<=n<=10^6

-10<= ai <= 10

下面是我的代码:

#include<stdio.h>


main()
{
 int t, j, k, l, sum;
 long long int num, out = 0;
 long long int ai[1000001];
 scanf("%d",&t);

 while(t--)
 {
    for(j=0;j<=num;j++)
    {   
    scanf("%lld",&ai[j]);
    }
    for(l=0;l<=num;l++)
    {

        for(k=l; k<=num; k++)
        {
          if(sum == 0)
          {
            num++;
          }
          else
          {
            sum = sum + ai[k];
          }

        }
        printf("%d", &num);
    }

 }
 return 0;
}

Answer 1

令 S[i] 为从索引 0 到索引 i 的元素之和(前缀和)。设置 S[-1] = 0。

您可以观察到，如果从索引 i 到索引 j (j > i) 的序列之和为 0，则 S[j] - S[i-1] = 0，或 S[j] = S[i-1 ].

为了解决这个问题，只需保留 S[i] (i=-1..n-1) 的值到总和频率的映射即可。如果特定的总和重复出现 k 次，您可以让 k 选择 2 种方法来配对索引以创建不同的序列。通过将所有索引配对方式相加，遍历所有键并检查最后的频率，就可以得到序列的总数。

对于插入和更新操作，映射的实现最多应为O(log n)。这将使您能够以 O(n log n) 的整体复杂度解决问题:前缀和 O(n)，插入/更新 map O (n log n)，遍历整个映射来总结结果 O(n)。

伪代码:

a[n] // Array of elements

m = new Map[Int->Int] // Frequency mapping

s = 0 // Prefix sum

m[s] += 1

for (i = 0; i < n; i++) {
  s += a[i] // Prefix sum of array of elements a
  m[s] += 1 // Increment frequency of the prefix sum by 1
}

out = 0

// Go through all key values in the map
m.traverse(function (key, value) {
    // Add the number of pairs of indices that has the same prefix sum
    out += value * (value - 1) / 2
})

return out