[磋商]政府决策及公共服务专利数据支撑专项-购买知识产权数据库账号法律诉讼类知识产权数据库账号成交公告

0220101
2023-04-23 07:39:11
# 题目

#### 原题链接

https://leetcode-cn.com/problems/number-of-good-pairs/

给你一个整数数组 nums ，返回其中 好对数 的数目。

好对数的定义是：nums[i] == nums[j] 且 i < j 。

示例 1：

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 个好对数：(0, 3), (0, 4), (3, 4), (2, 5) 。
注意，相同的元组应只计算一次。

示例 2：

输入：nums = [1,1,1,1]
输出：6
解释：数组中的每个元素都存在一个好对数。

示例 3：

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

提示：

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

#### 思路

• 从后向前遍历，记录出现过的数字，每次遍历到一个数字，用一个计数器，计数器初始值为0
• 遍历计数器，如果计数器大于0，说明后面还有相同的数字，就可以构成好对数，然后计数器-1
• 遍历完之后，返回计数器的值

#### 代码

```python
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
count = 0
for i in range(len(nums) - 1, -1, -1):
nums[i] -= 1
count += nums[i]
return count
```

我这个方法为什么不对呢，求大佬指点一下

你的方法没有正确地计数好对数。问题在于你的实现没有考虑到每个数字出现的次数。你需要一个更复杂的计数方法来计算好对数。

我们可以使用一个计数数组来记录每个数字出现的次数。然后通过组合数计算每个数字构成的好对数。

步骤：

1. 初始化一个计数数组 `cnt`，大小为101（因为数字范围是1到100），用于记录每个数字出现的次数。
2. 遍历数组 `nums`，更新计数数组。
3. 计算每个数字构成的好对数。对于每个数字 `x`，它能与 `x` 之前的每个不同的数字构成好对数，计数为 `cnt[x] * (cnt[x] - 1) // 2`。
4. 遍历计数数组，累加每个数字构成的好对数。

下面是改进后的代码：

```python
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
# 计数数组，记录每个数字出现的次数
cnt = [0] * 101
for num in nums:
cnt[num] += 1

result = 0
for i in range(1, 101):
if cnt[i] > 0:
# 计算每个数字构成的好对数
result += cnt[i] * (cnt[i] - 1) // 2

return result
```

解释：

1. 计数数组：`cnt` 数组用于记录每个数字在 `nums` 中出现的次数。
2. 遍历 `nums`：遍历 `nums` 数组，更新 `cnt` 数组。
3. 计算好对数：对于每个数字 `x`，它能与之前出现的每个不同的数字构成好对数。具体计算方法是 `cnt[x] * (cnt[x] - 1) // 2`，这是组合数的计算方式。
4. 累加结果：累加每个数字构成的好对数，最终返回结果。

这个方法能正确地计算出所有好对数。希望这能帮到你！如果有其他问题，请随时提问。