本文详解 LeetCode「好数对的数目」问题中基于频次统计的 O(n) 解法，重点剖析 count[a]++ 在累加过程中如何隐式计算每新增一个重复元素所贡献的新配对数。
本文详解 leetcode「好数对的数目」问题中基于频次统计的 o(n) 解法，重点剖析 `count[a]++` 在累加过程中如何隐式计算每新增一个重复元素所贡献的新配对数。
在解决「好数对的数目」（Number of Good Pairs）这类统计相同元素两两组合的问题时，暴力双重循环（O(n²)）虽直观，但效率较低。更优解法利用频次累计 + 后置自增的巧妙组合，在单次遍历中完成计数，时间复杂度降至 O(n)，空间复杂度为 O(1)（受限于值域）。
其核心逻辑在于：每当遇到一个值为 a 的元素时，count[a] 当前存储的是此前已出现过的 a 的个数；而 res += count[a]++ 表示：先将历史出现次数加到结果中，再将该值的计数加 1。
这恰好对应了“新增一个 a 能与之前所有 a 构成新配对”的数学本质——若 a 已出现 k 次，则第 (k+1) 次出现时，会新增 k 个新配对（即 (i₁, iₖ₊₁), (i₂, iₖ₊₁), ..., (iₖ, iₖ₊₁)）。
以输入 A = [1, 2, 3, 1, 1, 3] 为例，逐步追踪执行过程：
int res = 0, count[] = new int[101]; // 初始化全为 0
| 步骤 | a |
执行操作 |
res 变化 |
count[a] 变化（执行后） |
说明 |
|---|---|---|---|---|---|
| 1 | 1 |
res += count[1]++ → res += 0
|
0 | count[1] = 1 |
首次见 1，无历史配对 |
| 2 | 2 |
res += count[2]++ → res += 0
|
0 | count[2] = 1 |
首次见 2 |
| 3 | 3 |
res += count[3]++ → res += 0
|
0 | count[3] = 1 |
首次见 3 |
| 4 | 1 |
res += count[1]++ → res += 1
|
1 | count[1] = 2 |
第2个1，与前1个1组成1对 |
| 5 | 1 |
res += count[1]++ → res += 2
|
3 | count[1] = 3 |
第3个1，与前2个1组成2对 |
| 6 | 3 |
res += count[3]++ → res += 1
|
4 | count[3] = 2 |
第2个3，与前1个3组成1对 |
最终 res = 4，正确对应所有好对子：(0,3), (0,4), (3,4), (2,5)。
✅ 关键理解点：
-
count[a]++是后置自增，表达式值为自增前的count[a]，因此res += count[a]++等价于：res += count[a]; // 加入当前已有同值元素个数（即新元素可形成的新配对数） count[a]++; // 再更新频次
- 该解法隐含假设：数组元素范围为
[0, 100]（故new int[101]足够）。若题目含负数或更大数值（如[-10⁴, 10⁴]），需改用HashMap<integer integer></integer>或离散化处理：
public int numIdenticalPairs(int[] A) {
Map<Integer, Integer> count = new HashMap<>();
int res = 0;
for (int a : A) {
res += count.getOrDefault(a, 0);
count.put(a, count.getOrDefault(a, 0) + 1);
}
return res;
}⚠️ 注意事项：
- 原解法
int[101]是针对 LeetCode 本题约束（1 ≤ nums[i] ≤ 100）的优化特例，不可直接套用于通用场景； - 使用数组索引作为键的前提是值域小且非负，否则易引发
ArrayIndexOutOfBoundsException； -
count[a]++的副作用（修改状态）必须结合上下文理解，调试时建议逐行观察res和count数组变化。
这种“边遍历、边累计、边贡献”的思路，是频次统计类问题的经典范式，广泛应用于子数组和、重复元素计数、排列组合优化等场景。掌握其内在逻辑，远胜于记忆代码模板。
