本文详解 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]++ 是后置自增操作，其行为分为三步（原子性不可分割）：

1. 读取当前 count[a] 的值；
2. 将该值累加到 res（即 res += count[a]）；
3. 再将 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);
    }</integer>

  • 若已知数据范围但含负数，可做偏移映射（如 count[a + offset]）。
• 时间复杂度优势：O(n) vs 暴力 O(n²)，在大规模数据（如 n=10⁵）下性能差异显著。
• 空间权衡：固定数组 O(1) 空间（常数级），哈希表最坏 O(n) 空间，但更健壮。

✅ 总结

res += count[a]++ 并非直接“统计相同元素个数”，而是巧妙利用频次数组的当前计数值作为新元素可形成的配对数，借助后置自增保证“先用后增”。这是一种典型的贪心式计数模式：每遇到一个重复值，它立即与所有历史同值元素组成新配对，无需回溯。掌握此思想，可迁移至子数组和、逆序对、区间重叠等众多频次相关问题。