LeetCode 1512. 好数对的数目

约 3 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 阿里
标签
数组 哈希表 数学 计数

题目描述

✅ 1512. 好数对的数目

image-20260929084850022

题意分析

统计数组中满足 i < j 且 nums[i] == nums[j] 的下标对数量。要求两个不同位置，数值相同但位置不同可以形成多对。

每对按较小下标在前的顺序只计一次，不能把 (i,j) 与 (j,i) 算成两对，也不能让元素与自身配对。

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

核心思路

[!blue]

按右端点 j 从左到右计数。处理当前值之前，freq[value] 表示它在此前前缀出现的次数，也就是所有满足 i < j 且数值相同的位置数量。

若此前出现了 count 次，当前元素就与这 count 个位置分别形成一对，直接把 count 加入答案，无需逐一保存或枚举它们的下标。

结算后再将当前元素登记，使频次表仍表示下一轮的历史前缀。每个好数对只会在处理它的较大下标时出现一次，所以计数既满足顺序，也不会重复。

本轮贡献必须来自旧频次。Java 先把旧值保存在 count，Go 则直接在递增之前读取表值，两种写法含义一致。

解题步骤

  1. 创建空频次表，将答案设为零。
  2. 依次读取每个元素，查询它在此前出现的次数。
  3. 把旧次数加入答案，再将这个值的频次加一。
  4. 所有元素处理完后返回累计数量。

代码实现

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(u+1)$，其中 $u$ 是不同数值个数，保存它们的历史频次。

关键点总结

[!green]

  • 按较大下标结算，i < j 自动成立。
  • 同值的每个历史位置都是不同配对对象，频次就是当前贡献。
  • 旧频次负责计数，新频次留给之后的位置使用。

易错点总结

[!yellow]

  • 用递增后的频次计数，会把当前元素与自身也算成一对。
  • 只保存是否出现，或每次重复只加一，会漏掉多个相同历史位置的贡献。
  • Java 已经保存旧 count 后，写回表与累加旧值的顺序可互换；真正需要避免的是读取新频次作为本轮贡献。

相似题目

题目 难度 关联与区别
217. 存在重复元素 简单 原题只判断重复是否存在，本题每读到一个值，就把此前相同值的数量加入数对总数。
2001. 可互换矩形的组数 中等 同样按等价键计同类下标对，本题键是元素值，原题键是约分后的矩形长宽比。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/31181872
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！