---

1512. 好数对的数目

• 标签：数组、哈希表、数学、计数
• 难度：简单

题目链接

• 1512. 好数对的数目 - 力扣

题目大意

描述：给定一个整数数组 $nums$。如果 $nums[i] == nums[j]$ 且 $i < j$，则称 $(i, j)$ 为一个好数对。

要求：返回好数对的数量。

说明：

• $1 \le nums.length \le 100$。
• $1 \le nums[i] \le 100$。

示例：

• 示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始

• 示例 2：

输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对

解题思路

思路 1：哈希表计数

1. 核心思想

遍历数组，对每个元素，如果它之前出现过，那么它和之前的所有相同元素都能组成好数对。

因此用一个哈希表记录每个数字出现的次数。遍历时累加即可。

2. 具体步骤

第 1 步：$cnt = {}$，$ans = 0$。

第 2 步：遍历每个 $x$：

• $ans += cnt.get(x, 0)$。
• $cnt[x] = cnt.get(x, 0) + 1$。

第 3 步：返回 $ans$。

3. 举例说明

以 $nums = [1,2,3,1,1,3]$ 为例：

• $i=0$：$x=1$，$cnt[1]=0$，$ans=0$，$cnt[1]=1$。
• $i=1$：$x=2$，$cnt[2]=0$，$ans=0$，$cnt[2]=1$。
• $i=2$：$x=3$，$cnt[3]=0$，$ans=0$，$cnt[3]=1$。
• $i=3$：$x=1$，$cnt[1]=1$，$ans=1$，$cnt[1]=2$。
• $i=4$：$x=1$，$cnt[1]=2$，$ans=3$，$cnt[1]=3$。
• $i=5$：$x=3$，$cnt[3]=1$，$ans=4$，$cnt[3]=2$。

返回 $4$。

思路 1：代码

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        cnt = {}
        ans = 0
        for x in nums:
            ans += cnt.get(x, 0)
            cnt[x] = cnt.get(x, 0) + 1
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$，数字范围 $[1, 100]$。