本文详解 LeetCode「好数对」问题中基于频次累加的 O(n) 解法，通过 count[a]++ 的后置自增特性，在单次遍历中动态累计相同元素构成的配对数，并对比其原理、局限与适用边界。
本文详解 leetcode「好数对」问题中基于频次累加的 o(n) 解法，通过 `count[a]++` 的后置自增特性，在单次遍历中动态累计相同元素构成的配对数，并对比其原理、局限与适用边界。
在解决「好数对」（即满足 i 且 <code>nums[i] == nums[j] 的索引对数量）问题时，暴力双重循环（O(n²)）虽直观，但存在明显优化空间。更优解利用频次统计 + 后置自增技巧，在一次遍历中完成计数，时间复杂度降至 O(n)，空间复杂度为 O(1)（固定大小数组）。核心代码如下：
public int numIdenticalPairs(int[] A) {
int res = 0;
int[] count = new int[101]; // 假设所有元素 ∈ [0, 100]
for (int a : A) {
res += count[a]++;
}
return res;
}? 关键原理：count[a]++ 的执行顺序与语义
count[a]++ 是后置自增操作，其行为分为三步（原子性不可分割）：
-
读取当前
count[a]的值； -
将该值累加到
res（即res += count[a]）； -
再将
count[a]自增 1。
这意味着：每次遇到值为 a 的元素时，res 增加的是「此前已出现过多少个 a」——而这恰好等于该元素能与前面所有同值元素组成的“好数对”数量。
以示例数组 {1, 2, 3, 1, 1, 3} 逐步追踪：
| 步骤 | 当前元素 a
|
count[a]（执行前） |
res += count[a] |
count[a]（执行后） |
累加含义 |
|---|---|---|---|---|---|
| 1 | 1 | 0 | res = 0 + 0 = 0 |
1 | 第1个1 → 无前置1，新增0对 |
| 2 | 2 | 0 | res = 0 + 0 = 0 |
1 | 第1个2 → 新增0对 |
| 3 | 3 | 0 | res = 0 + 0 = 0 |
1 | 第1个3 → 新增0对 |
| 4 | 1 | 1 | res = 0 + 1 = 1 |
2 | 第2个1 → 可与前1个1配对 → +1对 |
| 5 | 1 | 2 | res = 1 + 2 = 3 |
3 | 第3个1 → 可与前2个1各配1对 → +2对 |
| 6 | 3 | 1 | res = 3 + 1 = 4 |
2 | 第2个3 → 可与前1个3配对 → +1对 |
最终 res = 4，完全匹配预期结果。
⚠️ 注意事项与局限性
-
数值范围硬编码风险：
new int[101]隐含假设0 ≤ nums[i] ≤ 100。若输入含负数、大于100的整数（如105或-5），将触发ArrayIndexOutOfBoundsException。 -
通用性改进方案：
- 使用
HashMap<integer integer></integer>替代固定数组，支持任意整数范围：Map<Integer, Integer> count = new HashMap<>(); for (int a : A) { res += count.getOrDefault(a, 0); count.put(a, count.getOrDefault(a, 0) + 1); } - 若已知数据范围但含负数，可做偏移映射（如
count[a + offset]）。
- 使用
- 时间复杂度优势：O(n) vs 暴力 O(n²)，在大规模数据（如 n=10⁵）下性能差异显著。
- 空间权衡：固定数组 O(1) 空间（常数级），哈希表最坏 O(n) 空间，但更健壮。
✅ 总结
res += count[a]++ 并非直接“统计相同元素个数”，而是巧妙利用频次数组的当前计数值作为新元素可形成的配对数，借助后置自增保证“先用后增”。这是一种典型的贪心式计数模式：每遇到一个重复值，它立即与所有历史同值元素组成新配对，无需回溯。掌握此思想，可迁移至子数组和、逆序对、区间重叠等众多频次相关问题。
