好数对的数目这道题几乎每个刷算法题的人都绕不过。它出现在各大题库的入门区间标签通常是数组和哈希表。题目本身一句话就能说清给你一个整数数组 nums数一数有多少对下标 (i, j)满足 i j 且 nums[i] nums[j]。别小看这短短一句话。它表面上考的是数数实际上把暴力枚举、哈希计数、组合数学三条典型路线全部浓缩在了一个小题目里。对于刚接触算法的同学这是绝佳的练手素材对于准备面试的开发者它也是快速热身、检验基本功的好样例。这篇文章我会从题目翻译开始把三种主流解法的思路、代码、复杂度一条条过一遍再把我实际踩过的坑和排查经验一并整理出来希望能让你一次性吃透这道题。1. 题目拆解这题到底在数什么1.1 先从示例看规则题目给出的典型示例是 nums [1,2,3,1,1,3]期望输出是 4。这个例子选得很有讲究几乎把关键信息都覆盖了。我们手动过一遍。数组里值 1 出现在下标 0、3、4 三个位置值 2 只出现在下标 1值 3 出现在下标 2、5。题目要求的数对 (i, j) 有两个硬性条件i j且 nums[i] nums[j]。先看值 1三次出现任选两个下标都能组成一对分别是 (0,3)、(0,4)、(3,4)一共 3 对。值 2只出现一次凑不出任何数对。值 3两次出现能组成 (2,5) 这么一对。三个贡献加起来 3 0 1 4和期望输出完全吻合。这里有一个必须想明白的点i j 这个约束本质上是在规定每个无序数对只按一种顺序计数。也就是说(0,3) 和 (3,0) 是同一种组合只数一次而且一个下标不能自己和自己组队比如 (3,3) 这种情况虽然 nums[3] 当然等于它自己但按照 i j 的要求它并不存在。很多新手在暴力解法里犯错根源就是没把这个约束落进循环边界里。1.2 隐藏条件和边界提前想清楚写代码之前先把输入的可能情况在脑子里过一遍能省下后面大量调试时间。空数组和只有一个元素的数组答案必然是 0因为凑不出任何满足 i j 的数对。所有元素全部相同比如长度为 5 的 [7,7,7,7,7]答案是 C(5,2) 10也就是任意两个位置都能配对。所有元素都不相同答案是 0。数组里有负数、有 0 也完全不影响思路因为判断条件是值相等跟大小、正负都没有关系。数组长度和值域范围也是关键信息。常见的版本里n 通常在 100 到 10^5 这个量级值域可能是 1 到 100也可能更宽。这两个数字直接决定你选哪种解法n 小暴力也能过n 大就必须上线性算法。后面第三节我会专门对比复杂度这里先记住一个结论动手写之前先读清楚数据范围这是所有算法题的第一步也是很多人在真实笔试里栽跟头的地方。2. 三种解法逐个对比2.1 暴力双层循环正确但不优雅最直觉的解法就是双层循环。外层 i 从左往右内层 j 从 i1 开始往右凡是 nums[i] nums[j] 就计数加一。def num_identical_pairs(nums): n len(nums) ans 0 for i in range(n - 1): for j in range(i 1, n): if nums[i] nums[j]: ans 1 return ans这个写法的正确性很好证明任何满足条件的数对 (i, j)会被且只会被外层 i 和内层 j 的组合访问到一次。内层从 i1 开始从机制上排除了 i j 的情况也排除了自己和自己配对。时间复杂度是 O(n^2)外层循环 n-1 次内层平均大约 n/2 次总比较次数约 n(n-1)/2。空间复杂度 O(1)连额外数组都不用。我不建议把这个解法当作最终答案提交但强烈建议把它当作正确性基准保留下来。尤其是后面写哈希优化时拿暴力版在小数据上对拍能快速发现优化版的问题。实测下来n 不超过 1000 时暴力完全没问题n 到 10^5 量级n^2 约等于 10^10 次操作任何语言的裸双层循环都会超时这时候优化就是必须的了。2.2 哈希表一边遍历一边计数暴力解法慢在哪慢在它把每一个数对都显式检查了一遍而大量比较其实是重复的——同一个值反复出现在不同位置比较结果都一样。优化的方向很明确既然我们要数的是相同值的两两组合那不如直接把每个值已经出现的次数记下来。核心思路是这样从左到右扫描数组当扫到当前元素 nums[i] 时它能够和已经出现过的、值等于 nums[i] 的所有位置分别组成一对。也就是说答案直接加上 freq[nums[i]]然后再把 freq[nums[i]] 自增一表示当前这个位置参与后续配对。from collections import defaultdict def num_identical_pairs(nums): freq defaultdict(int) ans 0 for x in nums: ans freq[x] freq[x] 1 return ans用示例 [1,2,3,1,1,3] 走一遍读到第一个 1freq[1] 是 0ans 加 0freq[1] 变 1读到 2freq[2] 是 0ans 不变freq[2] 变 1读到 3freq[3] 是 0ans 不变freq[3] 变 1读到第二个 1freq[1] 是 1ans 变 1freq[1] 变 2读到第三个 1freq[1] 是 2ans 变 3freq[1] 变 3读到第二个 3freq[3] 是 1ans 变 4freq[3] 变 2最终 ans 4正确。这里有一个顺序细节写错的人不少必须是先 ans freq[x]再 freq[x] 1。如果顺序反过来第一个出现的元素就会和自己配对白多算一组。比如数组 [5]正确答案是 0顺序写反会算出 1。这种错误非常隐蔽因为大部分测试用例里它不会让结果错得离谱但一旦暴露就让人摸不着头脑。单独跑一个元素的用例时才能一眼看穿。时间复杂度和空间复杂度都是 O(n)。哈希表的读写平均是 O(1)所以整个扫描是线性的。这种一边遍历、一边用历史信息更新答案的模式在算法题里出现频率极高后面第四节我会展开讲能迁移到哪些场景。2.3 组合公式统计频次后的数学收尾第三种解法的视角更高一层不要一个个数数对而是直接根据统计结果算贡献。假设某个值 v 在数组里出现了 c 次。这 c 个位置两两之间都能组成一个满足条件的数对因为不管选哪两个位置下标小的是 i下标大的是 j天然满足 i j。所以值 v 的贡献就是组合数 C(c, 2) c * (c - 1) / 2。把所有不同值的贡献加起来就是最终答案。from collections import Counter def num_identical_pairs(nums): cnt Counter(nums) ans 0 for c in cnt.values(): ans c * (c - 1) // 2 return ans还是拿示例验证1 出现 3 次贡献 32/2 32 出现 1 次贡献 03 出现 2 次贡献 21/2 1。总和 4。这一版和哈希边扫边数的版本本质上是同一个答案的两种计算方式。哈希版里每个值出现第 2 次时贡献 1第 3 次时贡献 2第 c 次时贡献 c-1累计起来正好是 0 1 2 ... (c-1) c(c-1)/2和组合公式一模一样。想明白这一点你会对这类问题有更深的理解很多在线累加的写法背后都对应着一个离线组合的数学公式。组合公式版本的代码更短逻辑也更清晰是我个人在实际做题时最喜欢提交的版本。它把数数对这个动作彻底转化成了统计频次 一次数学计算几乎不存在漏数或重复数的可能。3. 复杂度分析、边界处理与语言细节3.1 三种解法的时间和空间到底差多少同样是解决一个问题三种解法效率差距巨大用表格对比最直观解法时间复杂度空间复杂度适用场景暴力双层循环O(n^2)O(1)n ≤ 1000 左右或作为对拍基准哈希边扫边数O(n)O(n)通用最不容易写错频次统计 组合公式O(n)O(n)数据量大时最稳思路最清晰实际感受一下量级差异n 10^5 时O(n^2) 是 10^10 次比较即使每秒跑 10^8 次基本操作也需要上百秒而 O(n) 的哈希方案只需要 10^5 次读写毫秒级完成。刷题平台上常见的超时场景绝大多数都是明明该线性、却写成了平方甚至更糟。关于空间两种 O(n) 方案在最坏情况下所有元素各不相等会存下 n 个键值对这是不可避免的。如果题目额外限制了值域很小比如数值只可能在 1 到 100 之间那还有更轻量的写法直接用长度为 101 的数组代替字典连哈希开销都省了。def num_identical_pairs(nums): freq [0] * 101 # 当值域限定在 1..100 时可用 ans 0 for x in nums: ans freq[x] freq[x] 1 return ans这个数组版本严格来说空间是 O(101)相当于 O(1) 常数比字典版更省但前提一定是值域有界且已知。值域不确定或者跨度很大比如从 -10^9 到 10^9就必须用字典。我见过不少人在值域很大的题里硬开数组结果要么越界要么空间爆炸这个取舍一定要看题目约束来决定不能凭感觉。3.2 一个容易栽的坑答案会超过 int这是我在工程和刷题实践中都踩过的真实问题必须单独拎出来说。答案是 sum(c * (c - 1) / 2)最大值出现在所有元素都相同时等于 n(n-1)/2。当 n 10^5 时这个值是 4,999,950,000约 50 亿。而 32 位有符号整数的上限是 2,147,483,647大约 21 亿——明显装不下。所以在 Java 里用 int 存 ans 会溢出必须用 longC 里声明成 long long。Python 的整数是任意精度的不会溢出这也是 Python 对新手友好的原因之一但如果你在写 Java、C、Go 版本一定要把这一点提前考虑进去。还有一个小细节组合公式里 c * (c - 1) 是先乘后除在 Java/C 里如果 c 是 intc * (c - 1) 这一步就可能先溢出。稳妥的做法是先把 c 转成 64 位再计算或者干脆用哈希边扫边数的版本直接累加每次的贡献天然避免大数乘法。这个坑在真实笔试里尤其阴险——你能写对逻辑却可能因为一个类型声明错失满分。4. 常见错误、调试技巧与进阶变体4.1 新手最容易犯的错整理成一张速查表我把这道题相关的常见错误按现象、原因、修复整理成了一张表方便你排查时对照错误现象根本原因正确做法答案偏大且总是某个固定倍数内层循环从 0 开始把每对数对的正反顺序都数了内层 j 从 i1 开始或最后结果除以 2单元素数组算出 1把 freq[x] 1 写在 ans freq[x] 前面元素自己和自己配对先累加答案再更新频次大数组答案变成负数或明显异常32 位整数溢出答案用 long / long long 存储值域很大的题用了数组下标当键对输入约束判断失误改用哈希表暴力版能过、优化版反而错优化版逻辑写偏缺少验证手段保留暴力版作为对拍基准其中先更新频次再累加答案这条我多说两句。它的本质是把当前元素能与前面多少个相同元素配对误算成了当前元素能与包括自己在内的多少个相同元素配对。这种错误在数组长度为 1 时最容易暴露所以我一贯的调试习惯是小数据、边界数据、随机数据三管齐下而不是只拿题目示例测一下就提交。4.2 一个值得养成的习惯用暴力版对拍说一个我实测非常管用的方法论当你写完一个优化版本时不要只跑题目示例就提交。写一个简单的随机测试脚本生成几百组随机小数组同时跑暴力版和优化版对比输出是否完全一致。import random def brute(nums): n len(nums) ans 0 for i in range(n - 1): for j in range(i 1, n): if nums[i] nums[j]: ans 1 return ans def optimized(nums): freq {} ans 0 for x in nums: ans freq.get(x, 0) freq[x] freq.get(x, 0) 1 return ans for _ in range(1000): arr [random.randint(-5, 5) for _ in range(random.randint(0, 20))] assert brute(arr) optimized(arr), arr print(all ok)随机数组里涵盖了空数组、单元素、全相同、全不同、有负数等各种情况只要对拍通过95% 的边界问题都能提前暴露。这个习惯我带过不少新人坚持下来的人普遍反馈调试时间大幅减少。对拍脚本本身也值得收藏改一改函数名和输入生成规则就能复用到几乎所有算法题上。4.3 这道题能迁移出哪些进阶场景好数对的数目背后的思想可以平移到不少看起来完全不同的题上。第一类把值相等换成值互补。比如要求 i j 且 nums[i] nums[j] target这就是两数之和家族的问题。思路从看前面有没有相同的值变成看前面有没有 target - nums[i]哈希边扫边数的框架几乎原封不动。第二类把值相等换成差值固定。比如统计 i j 且 nums[j] - nums[i] k 的数对数量。做法是边扫边查 nums[i] - k 的出现次数同样是累计历史信息。这个变体和本题的哈希写法只差一个 key 的计算方式理解起来几乎没有额外成本。第三类统计频次后用组合公式的思维在很多按类别计数的题里都能用。比如给你一堆字符问能组成多少个相同字符对本质上就是这道题换了层皮。乘法原理、加法原理在这些题里反复出现熟练之后一眼就能识别。第四类需要维护历史信息的子数组类问题比如统计和为某个值的子数组个数。哈希表里存的是前缀和出现次数边扫边累加结构上和我上面写的 freq 累加一模一样。你会在越来越多的题里看到这个影子记录历史信息 当前值查表 更新表这个三段式是比这道题本身更值钱的财富。5. 写在最后的一点个人体会这道题我第一次写的时候也是暴力版当时觉得题目太简单不值得多花时间。后来在一次准备面试的模拟练习里被问到能不能优化到 O(n)才意识到这道题其实是在考察一个很重要的习惯看到数对计数先想清楚能不能不逐对枚举而是用频次或组合数直接算出来。从那以后我对所有计数类题目都会多问自己一句真的需要遍历每个组合吗我的建议是新手拿到这道题按这样的顺序练先写暴力版把题目规则彻底跑通再写哈希边扫边数版理解历史信息复用最后写组合公式版想明白两者为什么等价。三步走完这道题就不只是会做而是真正消化了。最后再分享一个小技巧不管最终解法多简洁提交前都拿暴力版在随机数据上对拍一轮。这个动作只需要几十秒却能把隐藏 bug 拦在提交之前。后面遇到更难的题目这个习惯的价值会越来越明显。上面给的验证脚本可以直接抄走改一改函数名就能用在其他题上。