怎么优化代码，第四个点超时了
#include <bits/stdc++.h>using namespace std;
int n;
const int N=2e5+10;
int a,b;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
b=i;
}
for(int j=1;j<=n;j++)
{
cin>>a;
}
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a-a==b-b)
{
res++;
}
}
}
cout<<res<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
}
求助大佬，只会暴力 你可以通过使用哈希表来优化你的代码。首先，我们可以将a-a[ i]和b-b[ i]的差值作为键，出现次数作为值，存储在一个哈希表中。然后在内层循环中，我们可以检查哈希表中是否存在a-a[ i]==b-b[ i]的情况，如果存在，则将对应的值累加到结果中。这样可以将时间复杂度优化为O(n)，避免了暴力枚举的O(n^2)复杂度。
下面是修改后的代码：
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
int a,b;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
b[ i]=i;
}
unordered_map<int, int> diffCount; // 哈希表用于存储差值及其出现次数
for(int j=1;j<=n;j++)
{
cin>>a;
}
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int diffA = a - a[ i];
int diffB = b - b[ i];
if(diffA == diffB)
{
res += diffCount; // 累加差值出现的次数
}
diffCount++; // 更新差值出现的次数
}
}
cout<<res<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
solve();
}
}
通过使用哈希表来存储差值及其出现次数，可以将时间复杂度优化为O(n)，避免了暴力枚举的O(n^2)复杂度，从而解决了超时的问题。
页:
[1]