优化此代码以检查和

Question

这就是我想在SPOJ解决的问题。我的时间限制超过了问题。我找不到优化算法的方法。你能给我一些提示吗。

以下是问题所在：

伦纳德必须找到连续数列的数目，使它们的和为零。 例如，如果序列是-5，2，-2，5，- 5，9 有三个这样的序列 2，-2 5，-5 2，-2，5，-5 因为这是莱纳德改写室友协议和摆脱谢尔顿荒谬条款的黄金机会，他不能输。所以他向你求助。别让他失望。 输入 第一行包含测试用例的T数 第二行包含n-特定测试用例中的元素数。 下一行包含n个元素，ai (1<=i<= n)由空格分隔。 输出 如果和为零的这类序列的数目。 约束条件 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

设Si是从索引0到索引I的元素之和(前缀和)。设置S1= 0。

可以观察到，如果从索引i到索引j (j > i)的序列之和为0，则Sj - Si-1 = 0，或Sj = Si-1。

为了解决这个问题，只需将Si的值映射到和的频率。如果一个特定的和重复了k次，你可以让k选择2种方式来组合索引来创建不同的序列。您可以通过总结所有配对索引的方法，通过遍历所有的键并检查末尾的频率来获得序列的总数。

对于insert和update操作，映射的实现最多应该是O(log )。这将允许您解决O(n log )的总体复杂性问题:前缀sum O(n)，插入/更新映射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

Answer 2

这是我的解决方案，类似于nhahtdh，但时间复杂度是O(n)

伪码：

        int pos[10000001];
        int neg[10000001];
        int sum = 0;
        int result = 0;
        for(int i = 0; i < arr.length; i++){
            sum += arr[i];
            if(sum > 0){
                result += pos[sum];
                pos[sum]++;

            }else{
                result += neg[-sum];
                neg[-sum]++;
            }


        }
        return result;