题解 | #谐距下标对#

题目链接

谐距下标对

题目描述

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

解题思路

本题要求我们寻找所有满足特定条件的下标对。直接使用两层循环的暴力解法时间复杂度为 $\mathcal{O}(n^2)$ ，会因超时而无法通过。我们需要找到一个更高效的数学解法。

核心思路：

条件转换：题目的核心等式是 a_j - a_i = j - i。这是一个关于数组值和下标之间关系的等式。我们可以通过移项来简化它： a_j - j = a_i - i
问题转化：这个转换非常关键。它告诉我们，如果两个下标 i 和 j 能组成谐距下标对，那么它们对应的 A[k] - k 的值是相等的。

因此，我们可以创建一个新的序列 $B$ ，其中每个元素 $B[k] = A[k] - k$ 。原问题就转化为了：在新序列 $B$ 中，有多少对相等的值？
使用哈希表进行计数：
- 我们可以遍历原始数组 $A$ ，对于每个元素 $A[i]$ ，计算出 $A[i] - i$ 的值。
- 使用一个哈希表（map 或 dictionary）来存储每个 $A[i] - i$ 的值出现了多少次。
- 遍历完整个数组后，哈希表中就记录了所有 A[k]-k 值的频率。
计算组合数：
- 假设某个值 v 在哈希表中记录的出现次数为 k。这意味着在序列 $B$ 中有 k 个元素的值为 v。
- 从这 k 个元素中，任意挑选两个，都可以组成一个满足条件的下标对。这是一个组合问题，数量为 $C(k, 2) = \frac{k \cdot (k-1)}{2}$ 。
- 我们遍历哈希表中的所有条目，对每个频率 k 计算其对应的组合数，并将它们全部累加起来，就得到了最终的答案。
- 注意，结果可能会超过32位整数的范围，需要使用64位整型（long long 或 long）来存储。

代码

cpp
java
python

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    
    map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        counts[a - i]++;
    }

    long long total_pairs = 0;
    for (auto const& [val, count] : counts) {
        if (count > 1) {
            total_pairs += (long long)count * (count - 1) / 2;
        }
    }

    cout << total_pairs << endl;

    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<>();

        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int diff = a - i;
            counts.put(diff, counts.getOrDefault(diff, 0) + 1);
        }

        long totalPairs = 0;
        for (int count : counts.values()) {
            if (count > 1) {
                totalPairs += (long)count * (count - 1) / 2;
            }
        }
        
        System.out.println(totalPairs);
    }
}

n = int(input())
# 处理n=0的特殊情况
if n == 0:
    print(0)
else:
    arr = list(map(int, input().split()))
    counts = {}
    
    for i in range(n):
        diff = arr[i] - i
        counts[diff] = counts.get(diff, 0) + 1
        
    total_pairs = 0
    for count in counts.values():
        if count > 1:
            total_pairs += count * (count - 1) // 2
            
    print(total_pairs)

算法及复杂度

算法：哈希表 / 频率计数
时间复杂度：我们需要遍历一次数组来计算差值并填充哈希表，这需要 $\mathcal{O}(n)$ 的时间。然后遍历哈希表，其大小最多为 $n$ 。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：哈希表在最坏情况下可能需要存储 $n$ 个不同的差值，因此空间复杂度为 $\mathcal{O}(n)$ 。