找相同数对

尺取法——同向扫描

#include <bits/stdc++.h> 
using namespace std;
const int N = 2e5 + 5;
int a[N];
int main (){
  int n , c; cin >> n >> c;       //放入数组，n:个数、c:差
  for(int i = 1 ; i <= n ; i ++) cin >> a[i];
  sort(a + 1 , a + 1 + n);        //数组排序
  long long ans = 0; //答案数量超过int，需要用long long
  for(int i=1,j=1,k=1; i <= n ; i ++) {
    while(j <= n && a[j] - a[i] < c ) j ++; //用j、k查找数字相同的区间
    while(k <= n && a[k] - a[i] <= c) k ++; //区间[j,k]内所有数字相同
    if(a[j]-a[i]==c && a[k-1]-a[i]==c && k-1>=1) ans += k - j;
  }
  cout << ans;
  return 0;
}

笔记：同向扫描的指针，遍历方向相同，但是速度不一，“快慢指针”形成一个“滑动窗口”，里面的元素相同，这样运算时不会漏掉每一对符合条件的数对