复杂度不对,代码需要重构
by Bant_Metor @ 2023-11-24 17:25:19
@[hyde_AC](/user/935979) 你时间复杂度假了,建议学习题解。
by Special_Tony @ 2023-11-24 17:25:37
@[hyde_AC](/user/935979)
如果要用双重循环,肯定会 `T `.
有几种做法(`map`做法好理解一些,因为我有些事情,来不及解释,请见谅):
```cpp
//双指针做法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,c,i,j=1,j2=1,sum,a[200005];
int main(){
scanf("%lld %lld",&n,&c);
for(i=1;i<=n;i++) scanf("%lld",a+i);
sort(a+1,a+1+n);
for(i=1;i<=n;i++){
while(j<=n&&a[j]-a[i]<=c) j++;
while(j2<=n&&a[j2]-a[i]<c) j2++;
if(a[j2]-a[i]==c&&a[j-1]-a[i]==c&&j>1)
sum+=j-j2;
}
printf("%lld\n",sum);
return 0;
}
```
```cpp
//map做法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,i,c,ans,a[2000005];
map <ll,ll> b;
int main(){
cin>>n>>c;
for(i=1;i<=n;i++){
cin>>a[i];
b[a[i]]++;
}
for(i=1;i<=n;i++)
if(a[i]>c) ans+=b[a[i]-c];
cout<<ans<<endl;
return 0;
}
```
by 2021zjhs005 @ 2023-11-24 17:27:41
@[hyde_AC](/user/935979) 也可以用双指针
by XiaoyuWan_ @ 2023-11-24 18:02:26
好像用二分和 map 会简单一些(我也没过)
by UzumakiBoruto @ 2023-11-25 10:28:49