LeetCode 1512 Number of Good Pairs（好数对）题解：暴力枚举与哈希表计数的三种思路

LeetCode 1512 Number of Good Pairs（好数对）题解：暴力枚举与哈希表计数的三种思路

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕 LeetCode 1512「好数对（Number of Good Pairs）」展开，完整讲解暴力枚举、组合数学求和、单次遍历滚动计数三种解法，并给出 Python / Java / C++ / JavaScript / C# / Go / Kotlin / Swift / Rust 九种语言的实现与复杂度分析。文中所有实现均可在本仓库对应目录中找到同题源码（见 cpp/1512-number-of-good-pairs.cpp、java/1512-number-of-good-pairs.java、go/1512-number-of-good-pairs.go、javascript/1512-number-of-good-pairs.js、kotlin/1512-number-of-good-pairs.kt），读完你将掌握"数对计数"类问题从 O(n²) 到 O(n) 的优化路径，以及哈希表频次统计的两种典型写法。

问题定义

给定一个整数数组nums，请返回数组中好数对的数量。

好数对的定义为：存在下标对(i, j)满足

• i < j
• nums[i] == nums[j]

换句话说，只要两个位置的值相等，且下标满足严格的前后顺序，就构成一个好数对。该题对应 LeetCode 第 1512 题（numIdenticalPairs），输入规模为1 <= nums.length <= 100，数组元素取值范围为1 <= nums[i] <= 100。

前置知识

在动手写代码之前，需要具备两点基础：

• 哈希表（Hash Map）：用字典 / 映射结构在 O(1) 时间内统计元素的出现频次。本题所有 O(n) 解法都依赖这一能力。
• 组合数学：理解从 n 个位置中选出 2 个位置的组合数公式n * (n - 1) / 2。当某个值出现 c 次时，这 c 个位置两两配对的数量恰好就是组合数 C(c, 2)。

解法一：暴力枚举（Brute Force）

核心思路

这是最直观的做法：穷举数组中所有可能的下标对(i, j)，逐一检查是否满足i < j且nums[i] == nums[j]，满足则计数加一。由于题目数组长度最大只有 100，O(n²) 的枚举完全可行。

算法步骤

1. 初始化计数器res为 0。
2. 使用两层嵌套循环：外层循环选取下标i，内层循环选取下标j（j从i + 1开始，天然保证i < j）。
3. 对每一对(i, j)，若nums[i] == nums[j]，则res加一。
4. 返回res。

各语言实现

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

public class Solution { public int numIdenticalPairs(int[] nums) { int res = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { res++; } } } return res; } }

class Solution { public: int numIdenticalPairs(vector<int>& nums) { int res = 0; for (int i = 0; i < nums.size(); i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums[i] == nums[j]) { res++; } } } return res; } };

class Solution { /** * @param {number[]} nums * @return {number} */ numIdenticalPairs(nums) { let res = 0; for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { res++; } } } return res; } }

public class Solution { public int NumIdenticalPairs(int[] nums) { int res = 0; for (int i = 0; i < nums.Length; i++) { for (int j = i + 1; j < nums.Length; j++) { if (nums[i] == nums[j]) { res++; } } } return res; } }

func numIdenticalPairs(nums []int) int { res := 0 for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { if nums[i] == nums[j] { res++ } } } return res }

class Solution { fun numIdenticalPairs(nums: IntArray): Int { var res = 0 for (i in nums.indices) { for (j in i + 1 until nums.size) { if (nums[i] == nums[j]) { res++ } } } return res } }

class Solution { func numIdenticalPairs(_ nums: [Int]) -> Int { var res = 0 for i in 0..<nums.count { for j in (i + 1)..<nums.count { if nums[i] == nums[j] { res += 1 } } } return res } }

impl Solution { pub fn num_identical_pairs(nums: Vec<i32>) -> i32 { let mut res = 0; for i in 0..nums.len() { for j in (i + 1)..nums.len() { if nums[i] == nums[j] { res += 1; } } } res } }

复杂度分析

• 时间复杂度：O(n²)，内层循环总共执行n * (n - 1) / 2次比较。
• 空间复杂度：O(1)，仅使用一个计数变量，没有额外数据结构。

解法二：哈希表 + 组合数学（Hash Map / Math）

核心思路

如果某个值在数组中出现c次，那么由该值构成的好数对数量，等于从这c个位置中任选 2 个的组合数，即c * (c - 1) / 2。因此可以先用哈希表统计每个值的频次，再对每个频次套用组合数公式求和。这个思路把问题从"枚举下标对"转化为"统计频次"，时间复杂度直接降到 O(n)。

算法步骤

1. 用哈希表统计每个数字出现的次数。
2. 遍历哈希表的每个频次c，将c * (c - 1) / 2累加到结果res。
3. 返回总和res。

各语言实现

class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: count = Counter(nums) res = 0 for num, c in count.items(): res += c * (c - 1) // 2 return res

public class Solution { public int numIdenticalPairs(int[] nums) { Map<Integer, Integer> count = new HashMap<>(); int res = 0; for (int num : nums) { count.put(num, count.getOrDefault(num, 0) + 1); } for (int c : count.values()) { res += c * (c - 1) / 2; } return res; } }

class Solution { public: int numIdenticalPairs(vector<int>& nums) { unordered_map<int, int> count; int res = 0; for (int num : nums) { count[num]++; } for (auto& [num, c] : count) { res += c * (c - 1) / 2; } return res; } };

class Solution { /** * @param {number[]} nums * @return {number} */ numIdenticalPairs(nums) { const count = {}; let res = 0; for (const num of nums) { count[num] = (count[num] || 0) + 1; } for (const c of Object.values(count)) { res += (c * (c - 1)) / 2; } return res; } }

public class Solution { public int NumIdenticalPairs(int[] nums) { var count = new Dictionary<int, int>(); int res = 0; foreach (int num in nums) { if (!count.ContainsKey(num)) count[num] = 0; count[num]++; } foreach (int c in count.Values) { res += c * (c - 1) / 2; } return res; } }

func numIdenticalPairs(nums []int) int { count := make(map[int]int) res := 0 for _, num := range nums { count[num]++ } for _, c := range count { res += c * (c - 1) / 2 } return res }

class Solution { fun numIdenticalPairs(nums: IntArray): Int { val count = mutableMapOf<Int, Int>() var res = 0 for (num in nums) { count[num] = count.getOrDefault(num, 0) + 1 } for (c in count.values) { res += c * (c - 1) / 2 } return res } }

class Solution { func numIdenticalPairs(_ nums: [Int]) -> Int { var count = [Int: Int]() var res = 0 for num in nums { count[num, default: 0] += 1 } for c in count.values { res += c * (c - 1) / 2 } return res } }

impl Solution { pub fn num_identical_pairs(nums: Vec<i32>) -> i32 { let mut count = HashMap::new(); let mut res = 0; for &num in &nums { *count.entry(num).or_insert(0) += 1; } for &c in count.values() { res += c * (c - 1) / 2; } res } }

复杂度分析

• 时间复杂度：O(n)，一次遍历统计频次 + 一次遍历求和。
• 空间复杂度：O(n)，哈希表最多存储数组中的不同元素个数。

解法三：哈希表边遍历边计数（Hash Map 单次遍历）

核心思路

前两种解法都需要"先统计完所有频次再计算"，其实可以合并为一步：遍历数组的过程中，每遇到一个新出现的值，它都能与此前出现过的每一个相同值构成一个新好数对。因此维护"到目前为止每个值出现的次数"，遍历时先把当前计数累加到结果，再更新计数即可。这样只需一趟扫描就能得到答案，代码也更简洁。

算法步骤

1. 初始化一个哈希表，记录每个数字到目前为止出现的次数。
2. 遍历数组中的每个数字：
   • 先把该数字当前的计数加到res（这就是新形成的好数对数量）；
   • 再把该数字在哈希表中的计数加一。
3. 返回res。

各语言实现

class Solution: def numIdenticalPairs(self, nums: List[int]) -> int: count = defaultdict(int) res = 0 for num in nums: res += count[num] count[num] += 1 return res

public class Solution { public int numIdenticalPairs(int[] nums) { Map<Integer, Integer> count = new HashMap<>(); int res = 0; for (int num : nums) { res += count.getOrDefault(num, 0); count.put(num, count.getOrDefault(num, 0) + 1); } return res; } }

class Solution { public: int numIdenticalPairs(vector<int>& nums) { unordered_map<int, int> count; int res = 0; for (int num : nums) { res += count[num]; count[num]++; } return res; } };

class Solution { /** * @param {number[]} nums * @return {number} */ numIdenticalPairs(nums) { const count = {}; let res = 0; for (const num of nums) { res += count[num] || 0; count[num] = (count[num] || 0) + 1; } return res; } }

public class Solution { public int NumIdenticalPairs(int[] nums) { var count = new Dictionary<int, int>(); int res = 0; foreach (int num in nums) { if (count.ContainsKey(num)) { res += count[num]; count[num]++; } else { count[num] = 1; } } return res; } }

func numIdenticalPairs(nums []int) int { count := make(map[int]int) res := 0 for _, num := range nums { res += count[num] count[num]++ } return res }

class Solution { fun numIdenticalPairs(nums: IntArray): Int { val count = mutableMapOf<Int, Int>() var res = 0 for (num in nums) { res += count.getOrDefault(num, 0) count[num] = count.getOrDefault(num, 0) + 1 } return res } }

class Solution { func numIdenticalPairs(_ nums: [Int]) -> Int { var count = [Int: Int]() var res = 0 for num in nums { res += count[num] ?? 0 count[num, default: 0] += 1 } return res } }

impl Solution { pub fn num_identical_pairs(nums: Vec<i32>) -> i32 { let mut count = HashMap::new(); let mut res = 0; for &num in &nums { res += *count.get(&num).unwrap_or(&0); *count.entry(num).or_insert(0) += 1; } res } }

复杂度分析

• 时间复杂度：O(n)，单次遍历完成全部计数。
• 空间复杂度：O(n)，哈希表存储已出现元素的历史频次。

三种解法对比与选型建议

解法	核心思想	时间复杂度	空间复杂度	适用场景
暴力枚举	双重循环穷举下标对	O(n²)	O(1)	数组极短（如 n ≤ 100）、追求代码直白
哈希表 + 组合数学	先统计频次，再套用 C(c, 2) 求和	O(n)	O(n)	需要清晰的数学推导、便于讲解组合公式
哈希表单次遍历	边遍历边累加历史计数	O(n)	O(n)	追求单趟扫描、代码最简洁

在实际面试中，建议先给出暴力解（作为 baseline），再演进到 O(n) 的哈希表方案；解法二与解法三在复杂度上等价，区别仅在于"先统计后求和"与"边遍历边累加"，二者都值得掌握。

常见陷阱（Common Pitfalls）

陷阱一：重复计数

好数对要求i < j，也就是说每对下标只能被计数一次。使用嵌套循环时，内层循环必须从i + 1开始而非从 0 开始，否则同一对(i, j)与(j, i)会被重复统计。同理，使用组合公式c * (c - 1) / 2时，公式本身已经按"无序二元组"去重，切勿再乘以 2。

陷阱二：32 位整数溢出

在 Java、C++、Go 等使用固定宽度整数的语言中，c * (c - 1)在 c 很大时可能溢出 32 位整数。应对方式有两种：一是将结果或乘法操作数声明为 64 位类型（如long/long long/int64）；二是调整运算顺序，先做除法再乘法（当 c 为偶数时c / 2 * (c - 1)，为奇数时(c - 1) / 2 * c）。本题约束下元素值域较小（1 <= nums[i] <= 100），频次 c 有限，一般不会触发溢出，但这一隐患在同类"组合计数"题中值得警惕。

仓库源码印证

本仓库为该题提供了多语言的完整实现，可作为本文三种解法的落地参照：

• java/1512-number-of-good-pairs.java：一份文件内依次给出 Brute Force、Combinations（组合公式）、滚动计数三种解法，并逐段注释了各自的复杂度，与本文三个小节一一对应。
• kotlin/1512-number-of-good-pairs.kt：同样包含 rolling count、count and use arithmetic sequence、brute force 三种实现。
• cpp/1512-number-of-good-pairs.cpp：实现了基于unordered_map的滚动计数法，对应解法三。
• go/1512-number-of-good-pairs.go 与 javascript/1512-number-of-good-pairs.js：给出暴力枚举实现，对应解法一。

仓库的 articles/README.md 对文章规范有明确约定：每篇题解至少包含一个与 NeetCode 视频解法一致的方案、必须给出时间与空间复杂度、尽可能覆盖所有相关解法。本文的结构（三种解法 + 复杂度分析 + 陷阱提示）正是按照这一规范组织的，读者可以参照此模板阅读仓库内其他题解文章。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode