1512. 好数对的数目

🟢   🔖  数组 哈希表 数学 计数  🔗 力扣 LeetCode

题目

Given an array of integers nums, return the number ofgood pairs.

A pair (i, j) is called good if nums[i] == nums[j] and i < j.

Example 1:

Input: nums = [1,2,3,1,1,3]

Output: 4

Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]

Output: 6

Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]

Output: 0

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

题目大意

给你一个整数数组 nums 。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。

返回好数对的数目。

示例 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

解释： 数组中的每组数字都是好数对

示例 3：

输入： nums = [1,2,3]

输出： 0

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

解题思路

1. 统计每个数字的出现次数：

   • 使用 Map 记录每个数字的出现次数。例如，对于 nums = [1,2,3,1,1,3]，我们得到：

     1 -> 3
     2 -> 1
     3 -> 2
     

2. 根据组合公式计算好数对：

   • 如果一个数字出现了 val 次，那么可以形成的好数对数量为：val * (val - 1) / 2

3. 累加所有数字的好数对：

   • 遍历 Map 中的值，将所有数字的好数对数量累加，得到结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 数组的长度。

  • 统计出现次数,遍历 nums 一次，时间复杂度为 O(n)。
  • 计算好数对，遍历 Map 的值，最坏情况下有 n 个不同的值，时间复杂度为 O(n)。

• 空间复杂度：O(n)，使用了 Map 存储数字及其出现次数，最坏情况下 nums 中所有数字都不同，空间复杂度为 O(n)。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function (nums) {
	// 用 Map 统计每个数字的出现次数
	let count = new Map();
	for (let num of nums) {
		count.set(num, (count.get(num) || 0) + 1);
	}

	let goodPairs = 0;
	// 遍历统计结果，计算每个数字能形成的好数对数量
	for (let val of count.values()) {
		if (val > 1) {
			goodPairs += (val * (val - 1)) / 2; // 组合公式
		}
	}

	return goodPairs;
};

相关题目

题号	标题	题解	标签	难度	力扣
2001	可互换矩形的组数		数组 哈希表 数学 2+	🟠	🀄️ 🔗
2083	求以相同字母开头和结尾的子串总数 🔒		哈希表 数学 字符串 2+	🟠	🀄️ 🔗