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 jnums[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]满足则计数加一。由于题目数组长度最大只有 100O(n²) 的枚举完全可行。算法步骤初始化计数器res为 0。使用两层嵌套循环外层循环选取下标i内层循环选取下标jj从i 1开始天然保证i j。对每一对(i, j)若nums[i] nums[j]则res加一。返回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 respublic 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(vectorint 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: Veci32) - 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)。算法步骤用哈希表统计每个数字出现的次数。遍历哈希表的每个频次c将c * (c - 1) / 2累加到结果res。返回总和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 respublic class Solution { public int numIdenticalPairs(int[] nums) { MapInteger, 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(vectorint nums) { unordered_mapint, 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 Dictionaryint, 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 mutableMapOfInt, 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: Veci32) - 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 单次遍历核心思路前两种解法都需要先统计完所有频次再计算其实可以合并为一步遍历数组的过程中每遇到一个新出现的值它都能与此前出现过的每一个相同值构成一个新好数对。因此维护到目前为止每个值出现的次数遍历时先把当前计数累加到结果再更新计数即可。这样只需一趟扫描就能得到答案代码也更简洁。算法步骤初始化一个哈希表记录每个数字到目前为止出现的次数。遍历数组中的每个数字先把该数字当前的计数加到res这就是新形成的好数对数量再把该数字在哈希表中的计数加一。返回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 respublic class Solution { public int numIdenticalPairs(int[] nums) { MapInteger, 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(vectorint nums) { unordered_mapint, 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 Dictionaryint, 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 mutableMapOfInt, 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: Veci32) - 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考