题解 | #谐距下标对#

题目链接

谐距下标对

题目描述

给定一个长度为 $n$ 的整数数组 $a$ 。若下标对 $(i, j)$ 满足 $1 \le i < j \le n$ 且 $a_j - a_i = j - i$ ，则称 $(i, j)$ 为一对谐距下标对。请计算数组中的谐距下标对数量。

解题思路

这是一个计数问题，直接使用暴力法（双重循环）检查所有下标对 $(i, j)$ 的时间复杂度为 $\mathcal{O}(n^2)$ ，在 $n$ 较大时会超时。我们需要寻找一种更高效的解法。

核心思想：公式变形

题目的核心条件是 $a_j - a_i = j - i$ 。我们可以对这个等式进行移项变形： $a_j - j = a_i - i$

这个变形是解题的关键。它告诉我们，如果一对下标 $(i, j)$ 是谐距下标对，那么它们对应的 “值-下标” 这个差是相等的。

问题转化

令 $b_k = a_k - k$ ，那么原问题就等价于：统计有多少对下标 $(i, j)$ 满足 $i < j$ 且 $b_i = b_j$ 。

这个问题就转化成了一个经典的频次统计问题。我们可以使用哈希表（map）来高效地解决。

算法步骤

初始化：创建一个哈希表 counts 用于存储 $b_k$ 值的出现次数，初始化一个长整型变量 ans 为0，用于累计结果。
遍历数组：遍历输入的数组 $a$ ，从下标 $i=0$ 到 $n-1$ 。
计算差值：对于每个元素 $a_i$ ，计算出其对应的差值 $v = a_i - i$ 。（注意：题目下标从1开始，编程时通常从0开始，只要保持一致即可。这里我们统一用0-based下标，即 $v=a_i-i$ ）。
累计配对：在将当前的差值 $v$ 计入哈希表之前，先检查哈希表中已经有多少个 $v$ 了。假设 counts[v] 的值是 $c$ ，这说明在 $i$ 之前已经有 $c$ 个下标 $k$ 满足 $a_k-k=v$ 。当前的 $a_i-i$ 可以与这 $c$ 个下标中的任意一个配对，形成 $c$ 个新的谐距下标对。因此，我们将 ans 加上 counts[v]。
更新频次：将 ans 更新后，再将当前差值 $v$ 的出现次数加1，即 counts[v]++。
最终结果：遍历完整个数组后，ans 中累计的就是所有谐距下标对的总数。

通过这种方式，我们只需一次遍历即可解决问题，时间复杂度大大降低。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    map<int, int> counts;
    long long ans = 0;
    
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        int diff = a - i;
        
        // 当前的数可以和之前所有差值相同的数配对
        if (counts.count(diff)) {
            ans += counts[diff];
        }
        
        // 更新当前差值的计数
        counts[diff]++;
    }
    
    cout << ans << '\n';
    
    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Map<Integer, Integer> counts = new HashMap<>();
        long ans = 0;
        
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int diff = a - i;
            
            // 当前的数可以和之前所有差值相同的数配对
            ans += counts.getOrDefault(diff, 0);
            
            // 更新当前差值的计数
            counts.put(diff, counts.getOrDefault(diff, 0) + 1);
        }
        
        System.out.println(ans);
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    counts = {}
    ans = 0
    
    for i in range(n):
        diff = a[i] - i
        
        # 当前的数可以和之前所有差值相同的数配对
        ans += counts.get(diff, 0)
        
        # 更新当前差值的计数
        counts[diff] = counts.get(diff, 0) + 1
        
    print(ans)

solve()

算法及复杂度

算法：哈希表
时间复杂度：我们只需要对数组进行一次遍历。在遍历过程中，对哈希表的操作（查找和更新）平均时间复杂度为 $\mathcal{O}(1)$ 。因此，总的时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：在最坏的情况下，数组中所有元素的 值-下标 差都不同，哈希表需要存储 $n$ 个键值对。因此，空间复杂度为 $\mathcal{O}(n)$ 。