怎么优化代码，第四个点超时了

lsmCC

#include <bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
int a[N],b[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        b[i]=i;
    }
    for(int j=1;j<=n;j++)
    {
        cin>>a[j];
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
       for(int j=i+1;j<=n;j++)
       {
        if(a[j]-a[i]==b[j]-b[i])
        {
            res++;

        }
       }
        
    }
    cout<<res<<endl;

    

}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

求助大佬，只会暴力

isdkz

你可以通过使用哈希表来优化你的代码。首先，我们可以将a[j]-a[ i]和b[j]-b[ i]的差值作为键，出现次数作为值，存储在一个哈希表中。然后在内层循环中，我们可以检查哈希表中是否存在a[j]-a[ i]==b[j]-b[ i]的情况，如果存在，则将对应的值累加到结果中。这样可以将时间复杂度优化为O(n)，避免了暴力枚举的O(n^2)复杂度。

下面是修改后的代码：

#include <bits/stdc++.h>
using namespace std;
int n;
const int N=2e5+10;
int a[N],b[N];
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[j];
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int diffA = a[j] - a[ i];
            int diffB = b[j] - b[ i];
            if(diffA == diffB)
            {
                res += diffCount[diffA]; // 累加差值出现的次数
            }
            diffCount[diffA]++; // 更新差值出现的次数
        }
    }
    cout<<res<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

通过使用哈希表来存储差值及其出现次数，可以将时间复杂度优化为O(n)，避免了暴力枚举的O(n^2)复杂度，从而解决了超时的问题。