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

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n;
   
4. const int N=2e5+10;
   
5. int a[N],b[N];
   
6. void solve()
   
7. {
   
8.     cin>>n;
   
9.     for(int i=1;i<=n;i++)
   
10.     {
    
11.         b[i]=i;
    
12.     }
    
13.     for(int j=1;j<=n;j++)
    
14.     {
    
15.         cin>>a[j];
    
16.     }
    
17.     int res=0;
    
18.     for(int i=1;i<=n;i++)
    
19.     {
    
20.        for(int j=i+1;j<=n;j++)
    
21.        {
    
22.         if(a[j]-a[i]==b[j]-b[i])
    
23.         {
    
24.             res++;
    
25. 
    
26.         }
    
27.        }
    
28.         
    
29.     }
    
30.     cout<<res<<endl;
    
31. 
    
32.    
    
33. 
    
34. }
    
35. int main()
    
36. {
    
37.     int t;
    
38.     cin>>t;
    
39.     while(t--)
    
40.     {
    
41.         solve();
    
42.     }
    
43. }

复制代码

求助大佬，只会暴力

isdkz

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

下面是修改后的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int n;
   
4. const int N=2e5+10;
   
5. int a[N],b[N];
   
6. void solve()
   
7. {
   
8.     cin>>n;
   
9.     for(int i=1;i<=n;i++)
   
10.     {
    
11.         b[ i]=i;
    
12.     }
    
13.     unordered_map<int, int> diffCount; // 哈希表用于存储差值及其出现次数
    
14.     for(int j=1;j<=n;j++)
    
15.     {
    
16.         cin>>a[j];
    
17.     }
    
18.     int res=0;
    
19.     for(int i=1;i<=n;i++)
    
20.     {
    
21.         for(int j=i+1;j<=n;j++)
    
22.         {
    
23.             int diffA = a[j] - a[ i];
    
24.             int diffB = b[j] - b[ i];
    
25.             if(diffA == diffB)
    
26.             {
    
27.                 res += diffCount[diffA]; // 累加差值出现的次数
    
28.             }
    
29.             diffCount[diffA]++; // 更新差值出现的次数
    
30.         }
    
31.     }
    
32.     cout<<res<<endl;
    
33. }
    
34. int main()
    
35. {
    
36.     int t;
    
37.     cin>>t;
    
38.     while(t--)
    
39.     {
    
40.         solve();
    
41.     }
    
42. }
    

复制代码

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