Question

memset问题,求解释

#include<iostream>
using namespace std;
int hash1[1000010];
int hash2[1000010];
int main()
{
int a,b,c,d;
int i,j;
while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
{
memset(hash1,0,sizeof(hash1));
memset(hash2,0,sizeof(hash2));//为什么超时,去掉一个改成for循环就不超

if((a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0))
{
printf("0\n");
continue;

}
int ans = 0, s;
for(i = 0; i <= 1000001; i++)
hash1[i] = hash2[i] = 0;
for(i = 1; i <= 100; i++)
{
for(j = 1; j <= 100; j++)
{
s = a * i * i + b * j * j;
if(s > 0)
hash1[s]++;
else
hash2[-s]++;
}
}
for(i = 1; i <= 100; i++)
{
for(j = 1; j <= 100; j++)
{
s = c * i * i + d * j * j;
if(s >= 0)
ans += hash2[s];
else
ans += hash1[-s];
}
}
printf("%d\n", 16 * ans);
}
return 0;
}

Answer 1

memset其实就是相当于for
把全部分的都做一次,复杂度是1000010
而你循环的话复杂度是和N有关的.n不可能永远是1000010,所以不会超时

追问

改成for(i = 0; i <= 1000001; i++)
hash1[i] = hash2[i] = 0;就不超时,
用memset就超时

追答

那你通过的时间是多少啊？可能是memset用时间比较多吧

追问

我删掉一个689ms两个都在超3000

追答

恩memset比较耗时间.