gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 17:42:09 24 4
gpt4 key购买 nike

这就是问题,我正在尝试在 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;
}

最佳答案

令 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

关于c - 优化此代码以检查总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20779217/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com