LeetCode 1512. 好数对的数目

2025-09-19 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1512. 好数对的数目

题意分析

给一个整数数组 nums，统计满足 nums[i] == nums[j] 且 i < j 的下标对 (i, j) 的个数。

两个条件各自的作用要分清。nums[i] == nums[j] 说明只有数值相等才成对，两个下标之间隔多远、中间夹了什么都无关紧要；i < j 则是去重条件——它保证同一对元素只被数一次（不会既数 (2, 5) 又数 (5, 2)），而不是什么额外的距离限制。把 i < j 误读成「必须相邻」或「距离受限」是常见的审题失误。

由此可以立刻得到一个纯数学的刻画：若某个数值出现了 c 次，这 c 个位置里任取两个都构成一对好数对，共 $\binom{c}{2} = c(c-1)/2$ 对。不同数值之间不可能配对，所以答案就是对每个数值的出现次数套这个组合数再求和。

约束里 nums.length <= 100，元素值在 1 到 100 之间。规模极小，$O(n^2)$ 的双重循环都能过——所以这题标记为「简单」。但它在面试里的意义是考察能否把「枚举配对」转化为「按频次计数」，这是从 $O(n^2)$ 到 $O(n)$ 的通用一跃，也是 1、560、974、454 等一大批题的共同内核。值域只有 100 这一点还额外提示：可以用长度 101 的数组代替哈希表，常数更小。

答案上界：100 个相同元素时是 $\binom{100}{2} = 4950$，int 绰绰有余。

边界：数组只有一个元素时答案为 0；所有元素互不相同时答案为 0；所有元素相同时答案为 $n(n-1)/2$。

解法：哈希表统计历史出现次数

核心思路

暴力是双重循环枚举所有 i < j 并比较，$O(n^2)$。瓶颈在于：对每个 j，内层都要重新扫一遍它前面的所有元素去数「有几个和我相等」。而这个数量其实可以边扫边维护，不需要回头看。

观察计数过程：从左到右遍历，当遍历到下标 j 时，它能与前面每一个值等于 nums[j] 的元素各组成一对好数对。也就是说，j 的贡献恰好等于「nums[j] 在 nums[0..j-1] 中出现的次数」。把所有下标的贡献加起来，每一对 (i, j) 都在 j 处被数了且只数了一次——i < j 这个条件在这里自动满足，因为我们只统计「已经走过的元素」。

于是维护一张频次表 freq，不变量写清楚：在处理下标 j 的那一刻（累加贡献之前），freq[v] 恰好等于数值 v 在 nums[0..j-1] 中的出现次数。每轮先读 freq[nums[j]] 累加进答案（这是 j 的贡献），再执行 freq[nums[j]]++ 把自己登记进去，把不变量从 j 推进到 j+1。

先查后写的顺序是本题唯一的顺序敏感点。如果先写后查，j 会把自己也算成「前面的相等元素」，每个下标都凭空多贡献 1，答案偏大 n。

顺带说明这个逐项累加与组合数公式的等价性：对某个出现 c 次的数值，它的 c 个位置依次贡献 0, 1, 2, ..., c-1，求和正好是 $c(c-1)/2 = \binom{c}{2}$。所以「边扫边累加」和「先统计频次再套公式」得到的是同一个答案，只是前者一趟完成、后者两趟。两种写法都可以，一趟版本更简洁，两趟版本更能体现组合计数的思路——面试时把这层等价关系讲出来，比只写代码更有说服力。

解题步骤

准备频次表：本题值域是 1 到 100，用 int[101] 是最优选择，查询是纯数组寻址、没有哈希与装箱开销。用 HashMap 也完全正确，且在值域未知或很大时是唯一选择——面试时可以先写哈希表版本，再补一句「值域已知有界，可以换成计数数组」。

单趟从左到右遍历：方向必须固定，这样「已遍历过的元素」才恰好对应 i < j 中的 i。

先读频次并累加答案：answer += freq[num]。此刻 freq[num] 表示 num 在当前元素之前出现了几次，正是当前下标能组成的好数对数量。

再把当前元素登记进表：freq[num]++。这一步必须在累加之后，否则会把自己和自己配对。

返回累计答案。不需要最后再遍历一次频次表——贡献已经在扫描过程中全部结算完毕。

以 nums = [1, 2, 3, 1, 1, 3] 走一遍。

初始：freq = {}，answer = 0。

num = 1（下标 0）：freq[1] = 0，答案 +0，仍为 0。登记后 freq = {1:1}。
num = 2（下标 1）：freq[2] = 0，答案 +0。登记后 freq = {1:1, 2:1}。
num = 3（下标 2）：freq[3] = 0，答案 +0。登记后 freq = {1:1, 2:1, 3:1}。
num = 1（下标 3）：freq[1] = 1，答案 +1 变成 1。这一对是 (0, 3)。登记后 freq[1] = 2。
num = 1（下标 4）：freq[1] = 2，答案 +2 变成 3。这两对是 (0, 4) 和 (3, 4)。登记后 freq[1] = 3。
num = 3（下标 5）：freq[3] = 1，答案 +1 变成 4。这一对是 (2, 5)。登记后 freq[3] = 2。

返回 4。用组合数公式验证：数值 1 出现 3 次，贡献 $3 \times 2 / 2 = 3$；数值 3 出现 2 次，贡献 $2 \times 1 / 2 = 1$；数值 2 出现 1 次，贡献 0。合计 3 + 1 + 0 = 4，与逐项累加的结果完全一致。

反例检验顺序：若把 freq[num]++ 提到累加之前，下标 0 的 1 会先让 freq[1] = 1 再累加 1，答案凭空多出 1；六个下标各多 1，最终返回 10 而不是 4。

代码实现

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

class Solution {
    public int numIdenticalPairs(int[] nums) {
        // freq[v]：数值 v 在当前元素之前出现的次数。
        Map<Integer, Integer> freq = new HashMap<>();
        int answer = 0;

        for (int num : nums) {
            int count = freq.getOrDefault(num, 0);
            // 先查：count 就是当前下标能与前面组成的好数对数量。
            answer += count;
            // 后写：顺序反了会把自己和自己配成一对。
            freq.put(num, count + 1);
        }

        return answer;
    }
}

func numIdenticalPairs(nums []int) int {
	// freq[v]：数值 v 在当前元素之前出现的次数。
	freq := map[int]int{}
	answer := 0

	for _, num := range nums {
		// 先查：map 中不存在时零值为 0，正好表示「前面没出现过」。
		answer += freq[num]
		// 后写：顺序反了会把自己和自己配成一对。
		freq[num]++
	}

	return answer
}

复杂度分析

时间复杂度：$O(n)$。单趟遍历，每个元素做一次哈希查询、一次加法、一次哈希写入，都是均摊常数。相比 $O(n^2)$ 的双重循环，收益来自「用一张表把内层扫描替换成一次查询」。若换成 int[101] 计数数组，常数还能再降一截。

空间复杂度：$O(\min(n, U))$，U 是值域大小。哈希表最多存下 n 个不同数值；本题值域只有 100，所以实际上限是 100，用固定长度的计数数组时是严格的 $O(1)$。

关键点总结

把「枚举配对」翻译成「按频次计数」，是本题唯一的算法思想，也是最值得迁移的一条。凡是「统计满足某种关系的下标对个数」的题，先想能不能对每个右端点问「前面有多少个能和我配」，这样 $O(n^2)$ 就能降到 $O(n)$。

i < j 不是距离限制，而是去重手段。用「只统计已遍历元素」的扫描方式，这个条件自动满足，不需要写任何额外判断，也不需要最后除以 2。

先查后写。这是所有「边扫边配对」类题目的固定顺序：查表结算的是「我与前面所有人」的配对，先写会把自己算进去。

一趟累加与组合数公式 $\binom{c}{2}$ 等价，因为 0 + 1 + ... + (c-1) = c(c-1)/2。两种写法都对，能说清等价关系说明真的理解了计数结构，而不是背模板。

值域已知有界时用计数数组代替哈希表。本题值域 1..100，int[101] 更快、更省。面试时主动提出这个优化，是「知道数据特征能换来常数优化」的体现。

Go 的 map 读取不存在的键返回零值，所以 answer += freq[num] 可以省掉存在性判断；Java 则要用 getOrDefault，直接 get 会返回 null 并在拆箱时抛空指针。

易错点总结

先写后查（把 freq[num]++ 提到累加之前）：nums = [1,2,3,1,1,3] 中每个下标都多贡献 1，返回 10 而不是 4。

Java 里用 freq.get(num) 而不是 getOrDefault：首次遇到某个数值时返回 null，answer += null 在自动拆箱时抛 NullPointerException。

用双重循环但内层从 0 开始而不是 i + 1：每对被正反各数一次，nums = [1,1,1] 返回 6 而正确答案是 3；若再忘记除以 2 就直接翻倍。

把 i < j 误读成「相邻」：nums = [1,2,3,1,1,3] 只会数出 (3,4) 这一对，返回 1 而不是 4。

最后再遍历频次表用公式却又保留了扫描中的累加：两套计数叠加，答案翻倍，[1,1,1] 返回 6 而不是 3。两种写法只能选一种。

用公式时写成 c * (c - 1) 忘了除以 2：nums = [1,1,1] 返回 6 而不是 3，所有答案都是正确值的两倍。

用 int[100] 而不是 int[101]：题目值域是 1 到 100，nums 中出现 100 时 freq[100] 越界。计数数组长度必须是「最大值 + 1」。

把值当下标却没考虑负数或超大值：本题保证 1..100 所以安全，但把同样代码套到允许负数或值域 $10^9$ 的变体上会立刻越界，那时必须换回哈希表。

答案变量用了 short 或在中途取模：100 个相同元素时答案 4950 虽不溢出，但若把规模放大到 $10^5$，$\binom{10^5}{2} \approx 5 \times 10^9$ 就会超出 int，需要 long。

对数组排序后统计相邻相同段：排序本身是 $O(n \log n)$ 且破坏了原下标，虽然按段长套组合公式仍能得到正确数量，但比 $O(n)$ 的计数写法更慢，且在需要返回具体下标对的变体里彻底失效。

相似题目

题目	难度	考察点
1. 两数之和	简单	同为「边扫边查历史表」，但配对键是 `target - num` 且要返回具体下标
217. 存在重复元素	简单	只问是否存在重复，命中即可提前返回，不需要累加计数
219. 存在重复元素 II	简单	增加了下标距离不超过 `k` 的限制，表里要存最近一次出现的位置而非次数
454. 四数相加 II	中等	四个数组分成两半各求和入表，考察如何用分组把 $O(n^4)$ 降到 $O(n^2)$
1010. 总持续时间可被 60 整除的歌曲	中等	配对键从「相等」变成「模 60 互补」，还要单独处理余数为 0 的自配情形
2352. 相等行列对	中等	把整行整列序列化成键再计数，考察如何为复合结构设计哈希键