LeetCode 题解工作台
好数对的数目
给你一个整数数组 nums 。 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i j ，就可以认为这是一组 好数对 。 返回好数对的数目。 示例 1： 输入： nums = [1,2,3,1,1,3] 输出： 4 解释： 有 4 组好数对，分别是 (0,3), (0,4)…
4
题型
9
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
遍历数组，对于每个元素 ，计算 之前有多少个元素与其相等，即为 与之前元素组成的好数对的数目。遍历完数组后，即可得到答案。 时间复杂度 ，空间复杂度 。其中 为数组长度，而 为数组中元素的取值范围。本题中 $C = 101$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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 <= 1001 <= nums[i] <= 100
解题思路
方法一：计数
遍历数组，对于每个元素 ，计算 之前有多少个元素与其相等，即为 与之前元素组成的好数对的数目。遍历完数组后，即可得到答案。
时间复杂度 ，空间复杂度 。其中 为数组长度，而 为数组中元素的取值范围。本题中 。
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
ans = 0
cnt = Counter()
for x in nums:
ans += cnt[x]
cnt[x] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) due to a single pass through the array and hash operations. Space complexity is O(k) where k is the number of unique elements in nums, bounded by 100 per constraints. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you recognize a counting or frequency pattern here?
- question_mark
Consider using a hash map to avoid nested loops.
- question_mark
Ask yourself if you can calculate pairs without generating them explicitly.
常见陷阱
外企场景- error
Double-counting pairs by iterating over all i < j combinations.
- error
Forgetting that i must be less than j, not just matching values.
- error
Using nested loops unnecessarily instead of leveraging hash counts.
进阶变体
外企场景- arrow_right_alt
Count good pairs where i > j instead of i < j, adjusting logic accordingly.
- arrow_right_alt
Determine number of good triplets (i < j < k) with equal values using extended frequency counting.
- arrow_right_alt
Compute good pairs under a modulo constraint on the values to test handling of hash keys.