BGN27 谐距下标对

思路

先想一个问题：什么叫"谐距"？题目说的是下标 ，满足 ，也就是两个元素的"值的差"恰好等于"下标的差"。你可以理解成：如果把数组画在坐标系上，这两个点刚好在同一条斜率为 1 的直线上。

那怎么找这样的下标对呢？暴力枚举所有 肯定能做，但 在数据量大的时候就扛不住了。

关键转化

把条件 移项一下：

$$

发现了吗？只要定义 ，那问题就变成了：数组 中有多少对相等的元素？

这就是经典的"计数相同元素对数"问题了。用哈希表统计每个值出现的次数 ，每个值贡献 对，加起来就是答案。

举个例子

输入 [1, 2, 3, 4, 5, 6]，计算 （0 下标）：

0 1 2 3 4 5
1 2 3 4 5 6
1 1 1 1 1 1

值全是 1，出现 6 次，所以答案是 。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    unordered_map<int,long long> mp;
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        mp[x-i]++;
    }
    long long cnt=0;
    for(auto&[k,v]:mp){
        cnt+=v*(v-1)/2;
    }
    printf("%lld\n",cnt);
    return 0;
}

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        HashMap<Integer,Long> mp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            int key = x - i;
            mp.merge(key, 1L, Long::sum);
        }
        long cnt = 0;
        for (long v : mp.values()) {
            cnt += v * (v - 1) / 2;
        }
        System.out.println(cnt);
    }
}

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(x - i for i, x in enumerate(a))
print(sum(v * (v - 1) // 2 for v in c.values()))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    const mp = new Map();
    for (let i = 0; i < n; i++) {
        const key = a[i] - i;
        mp.set(key, (mp.get(key) || 0) + 1);
    }
    let cnt = 0;
    for (const v of mp.values()) {
        cnt += v * (v - 1) / 2;
    }
    console.log(cnt);
});

复杂度

  • 时间复杂度：，遍历一次数组建哈希表，再遍历一次哈希表求和。
  • 空间复杂度：，哈希表最多存 个不同的键。

总结

这题的核心就一个等式变形： 变成 。一旦想到定义 ，问题就退化成了"数组里有多少对相等元素"，哈希表计数走起， 搞定。遇到"两个量的差等于另外两个量的差"这类条件，移项凑同侧是个很常用的套路，值得记住。