题目链接

数对计数

题目描述

给定一个长度为 n 的整数序列 a 和一个整数常数 c，统计序列中有多少个有序数对 (i, j) 满足 1 <= i, j <= n 且 a[i] - a[j] = c。

输入描述:

  • 第一行输入两个整数 n 和 c (, )。
  • 第二行输入 n 个整数，表示序列 a ()。

输出描述:

  • 输出一个整数，表示满足条件的有序数对数量。

示例 输入:

5 2
1 3 3 4 5

输出:

4

说明:

  • 值为 3 的元素（a_i）有两个，值为 1 的元素（a_j）有一个。3 - 1 = 2。这构成了 2 * 1 = 2 对 (i,j)。
  • 值为 5 的元素（a_i）有一个，值为 3 的元素（a_j）有两个。5 - 3 = 2。这构成了 1 * 2 = 2 对 (i,j)。
  • 总计 2 + 2 = 4 对。

解题思路

本题的目标是计数满足 a[i] - a[j] = c 的有序数对 (i, j) 的数量。关键点在于，题目对索引 i 和 j 没有顺序要求，它们可以是任意 1 到 n 之间的值。

这启发我们从值的角度来思考问题。对于序列中的任意一个值 v_i，它能和多少个 v_j 配对呢？根据条件 a[i] - a[j] = c，我们知道 v_j 必须等于 v_i - c。

因此，问题转化为：对于序列中出现的每一个唯一值 v，它能作为数对中的 a[i]，而 v - c 作为 a[j]。如果 v 在序列中出现了 count(v) 次，v - c 出现了 count(v - c) 次，那么它们总共可以组成 count(v) * count(v - c) 个满足条件的 (i, j) 数对。

我们可以通过一个两遍扫描的算法来解决：

  1. 第一遍扫描 - 频率统计：

    • 创建一个哈希表（C++中的 map，Java中的 HashMap，Python中的 dict）。
    • 遍历整个输入序列，统计每个数字出现的次数，并存入哈希表中。

  2. 第二遍扫描 - 计算结果：

    • 初始化一个长整型 result 计数器为 0。
    • 遍历哈希表中的每一个键值对 (v, count_v)。
    • 对于每个 v，计算出它需要配对的目标值 target = v - c。
    • 在哈希表中查找 target 的出现次数 count_target。
    • 如果 target 存在，将 count_v * count_target 的乘积累加到 result 中。

这个算法高效地解决了问题，避免了 的暴力搜索。

代码

#include <iostream>
#include <map>

using namespace std;

int main() {
    int n;
    long long c;
    cin >> n >> c;
    map<long long, int> counts;
    for (int i = 0; i < n; ++i) {
        long long num;
        cin >> num;
        counts[num]++;
    }

    long long result = 0;
    for (auto const& [val, num_val] : counts) {
        long long target = val - c;
        if (counts.count(target)) {
            result += (long long)num_val * counts.at(target);
        }
    }
    cout << result << endl;
    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long c = sc.nextLong();
        HashMap<Long, Integer> counts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long num = sc.nextLong();
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        long result = 0;
        for (Map.Entry<Long, Integer> entry : counts.entrySet()) {
            long val = entry.getKey();
            long num_val = entry.getValue();
            long target = val - c;
            if (counts.containsKey(target)) {
                result += num_val * counts.get(target);
            }
        }
        System.out.println(result);
        sc.close();
    }
}

def main():
    n, c = map(int, input().split())
    nums = list(map(int, input().split()))
    
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
        
    result = 0
    for val, num_val in counts.items():
        target = val - c
        if target in counts:
            result += num_val * counts[target]
            
    print(result)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 哈希表/映射（两遍扫描频率计数）
  • 时间复杂度:
    • C++: 。第一遍构建 std::map 需要 ，第二遍遍历 map 需要 。整体由第一遍主导。K 是序列中不同元素的数量。
    • Java/Python: 。第一遍构建哈希表需要 ，第二遍遍历需要 。整体为 。
  • 空间复杂度: ，用于存储哈希表，K 是序列中不同元素的数量。