题目描述
思路解析
一句话答案：LeetCode 1512 好数对的数目：数出值相等且 i＜j 的下标对。用哈希计数边扫边加，每到一个值先把答案加上它之前出现过的次数、再登记自己，一遍扫完，时间 O(n)。
同值又前后成对的下标，一共几组
给你一个数组 nums，数出有多少对下标 (i, j) 满足：i 排在 j 前面，即 i＜j；两个位置的数相等，nums[i] 等于 nums[j]。这样算一组好数对，返回总数。题面例子 nums=[1,2,3,1,1,3]，值 1 落在下标 0、3、4，值 3 落在下标 2、5，同值位置两两配，得到 (0,3)、(0,4)、(3,4)、(2,5) 共 4 组。
每一对都拎出来比，n 大了要比多少次
把每一对下标都拎出来比：外层定 i、内层定 j＞i，看两值等不等，相等计一组。n 个数要验证 n(n−1)/2 对，量级是 O(n²)。长度到一百还行，双重循环上几万个数就明显慢——力气全花在核对每一对，没利用『好数对无非是同一个值的几个位置互相配』这层结构。
为什么记住『前面出现过几次』就够了
好数对只在值相同的位置之间产生，抓住这点就绕开逐对枚举。维护计数表 cnt，cnt[x] 记值 x 到当前为止出现过几次。指针从左往右走，每落到一个值 x，此刻 cnt[x] 正好是它前面的同值个数，当前位置能和那些位置各配一组，于是把 cnt[x] 加进答案，再让 cnt[x] 自增 1 登记自己。一遍走完就是全部好数对。
先加旧计数还是先登记自己，顺序要命
先后不能颠倒：必须先 ans += cnt[x]，再 cnt[x] += 1。根子在 i＜j——当前位置只允许和排在它前面的同值配。先累加，用的是还没算上自己的旧计数，配到的全是前面的位置；若反过来先自增再累加，就把自己也数进了 cnt[x]，凭空多配出当前位置和自己这一组，答案就多出一截。
[1,2,3,1,1,3] 扫下来，4 组是怎么冒出来的
跟着 nums=[1,2,3,1,1,3] 走，ans 从 0 起、cnt 空。到值 1（下标 0）：cnt[1] 是 0，ans 加 0 仍 0，cnt[1] 变 1。到值 2（下标 1）：cnt[2] 是 0，ans 不动，cnt[2] 变 1。到值 3（下标 2）：cnt[3] 是 0，ans 仍 0，cnt[3] 变 1。到值 1（下标 3）：cnt[1] 已是 1，ans 加 1 变 1，cnt[1] 变 2。到值 1（下标 4）：cnt[1] 已是 2，ans 加 2 变 3，cnt[1] 变 3。到值 3（下标 5）：cnt[3] 已是 1，ans 加 1 变 4，cnt[3] 变 2。扫完 ans=4，正是值 1 配 3 组、值 3 配 1 组之和。
扫一遍就够，全相同和全不同各配几组
指针把数组扫一遍，每格做查表、累加、自增三个常数操作，共 n 次，时间 O(n)，比双重循环的 O(n²) 快一整档。空间看计数表：C++、Java 的值只在 1 到 100，用长度 101 的定长数组，和 n 无关是 O(1)；Python 的 Counter 最坏装 n 个键是 O(n)。两种极端：nums=[1,1,1,1] 四个相同数是 4×3/2=6 组；nums=[1,2,3] 互不相同答案 0。只有重复值才产生好数对，出现 c 次固定贡献 c×(c−1)/2 组。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句:每到一个数 x,先把答案加上「前面同值的个数」cnt[x],再让 cnt[x] 自增 1。一遍扫描就能数出全部好数对。下面每帧都在套这句。
总览 · 数组 + 空计数表：先看清画面。上面是数组 nums = [1,2,3,1,1,3],一共 6 个数。右边那张计数表 cnt 现在是空的,它会记下每个值出现过几次。答案 ans 从 0 起步。接下来紫色指针从下标 0 一格一格往右走,每到一个数,就先看计数表里这个值已经有几个,把这么多对好数对加进 ans,再把当前这格登记进表。先从第 0 位开始。
第 0 位 · 查 nums[0] = 1：紫色指针落在下标 0,值是 1。去计数表里一查,前面一个 1 都还没出现过,cnt[1] 是 0。没有同值的老位置可配,所以这一格暂时一对也凑不出来,ans 不会变。但它要先把自己登记进表,好让后面再遇到 1 时能和它配。
第 0 位 · 累加 +0：前面没有同值,这一格给 ans 加 0,答案仍然是 0。这很正常:每个值第一次出现时都配不成对,它的作用是先入表、给后来者当配对对象。
第 0 位 · 登记 cnt[1] = 1：最后把当前这格登记进计数表:值 1 的次数从 0 加到 1,下标 0 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 1,就能把现在这个 0 也算成它的一个配对对象。继续看下一格。
第 1 位 · 查 nums[1] = 2：紫色指针落在下标 1,值是 2。去计数表里一查,前面一个 2 都还没出现过,cnt[2] 是 0。没有同值的老位置可配,所以这一格暂时一对也凑不出来,ans 不会变。但它要先把自己登记进表,好让后面再遇到 2 时能和它配。
第 1 位 · 累加 +0：前面没有同值,这一格给 ans 加 0,答案仍然是 0。这很正常:每个值第一次出现时都配不成对,它的作用是先入表、给后来者当配对对象。
第 1 位 · 登记 cnt[2] = 1：最后把当前这格登记进计数表:值 2 的次数从 0 加到 1,下标 1 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 2,就能把现在这个 1 也算成它的一个配对对象。继续看下一格。
第 2 位 · 查 nums[2] = 3：紫色指针落在下标 2,值是 3。去计数表里一查,前面一个 3 都还没出现过,cnt[3] 是 0。没有同值的老位置可配,所以这一格暂时一对也凑不出来,ans 不会变。但它要先把自己登记进表,好让后面再遇到 3 时能和它配。
第 2 位 · 累加 +0：前面没有同值,这一格给 ans 加 0,答案仍然是 0。这很正常:每个值第一次出现时都配不成对,它的作用是先入表、给后来者当配对对象。
第 2 位 · 登记 cnt[3] = 1：最后把当前这格登记进计数表:值 3 的次数从 0 加到 1,下标 2 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 3,就能把现在这个 2 也算成它的一个配对对象。继续看下一格。
第 3 位 · 查 nums[3] = 1：紫色指针落在下标 3,值是 1。去计数表里一查,前面已经出现过 1 个 1,它们的位置是下标 0,现在被标成绿色。这 1 个位置每一个都能和当前的下标 3 配成一组好数对,因为它们值相同、又都排在 3 前面。所以这一格会新增 1 组。
第 3 位 · 累加 +1：把这新增的 1 组加进答案:ans 从 0 变成 1。绿色那 1 个位置分别和下标 3 组成了好数对。注意我们只在这里加 cnt[1] 这么多,不多不少,正好是前面同值的个数,既不会漏配、也不会重复数同一对。
第 3 位 · 登记 cnt[1] = 2：最后把当前这格登记进计数表:值 1 的次数从 1 加到 2,下标 3 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 1,就能把现在这个 3 也算成它的一个配对对象。继续看下一格。
第 4 位 · 查 nums[4] = 1：紫色指针落在下标 4,值是 1。去计数表里一查,前面已经出现过 2 个 1,它们的位置是下标 0、3,现在被标成绿色。这 2 个位置每一个都能和当前的下标 4 配成一组好数对,因为它们值相同、又都排在 4 前面。所以这一格会新增 2 组。
第 4 位 · 累加 +2：把这新增的 2 组加进答案:ans 从 1 变成 3。绿色那 2 个位置分别和下标 4 组成了好数对。注意我们只在这里加 cnt[1] 这么多,不多不少,正好是前面同值的个数,既不会漏配、也不会重复数同一对。
第 4 位 · 登记 cnt[1] = 3：最后把当前这格登记进计数表:值 1 的次数从 2 加到 3,下标 4 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 1,就能把现在这个 4 也算成它的一个配对对象。继续看下一格。
第 5 位 · 查 nums[5] = 3：紫色指针落在下标 5,值是 3。去计数表里一查,前面已经出现过 1 个 3,它们的位置是下标 2,现在被标成绿色。这 1 个位置每一个都能和当前的下标 5 配成一组好数对,因为它们值相同、又都排在 5 前面。所以这一格会新增 1 组。
第 5 位 · 累加 +1：把这新增的 1 组加进答案:ans 从 3 变成 4。绿色那 1 个位置分别和下标 5 组成了好数对。注意我们只在这里加 cnt[3] 这么多,不多不少,正好是前面同值的个数,既不会漏配、也不会重复数同一对。
第 5 位 · 登记 cnt[3] = 2：最后把当前这格登记进计数表:值 3 的次数从 1 加到 2,下标 5 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 3,就能把现在这个 5 也算成它的一个配对对象。六个位置全部扫完了。
完成 · 好数对 = 4：六个位置都扫完了,回看一遍:值 1 出现在下标 0、3、4 三处,两两配出 (0,3)、(0,4)、(3,4) 共 3 组;值 3 出现在下标 2、5 两处,配出 (2,5) 共 1 组;值 2 只出现一次,配不成对。加起来 3 加 1 等于 4,和题面列出的 4 组好数对完全对上。整道题的窍门就一句:扫描时每到一个数,先用计数表里它前面同值的个数给答案加分,再把自己登记进表,线性时间就数完了。
边界:单个数为 0;四个相同数贡献 6 组(C(4,2));三个互不相同为 0。只有重复值才产生好数对。
面试重点:一个值出现 c 次贡献 C(c,2)=c×(c−1)/2(也可先计数再套公式);可改用排序分段统计但慢一档;三语言差别在 Python 用 Counter 分两行、C++/Java 用定长数组并合成 cnt[x]++。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(n)，n 是数组长度。指针从左扫到右,每个位置只做一次查表、一次累加、一次自增,都是常数操作,总共 n 次,所以是线性的 O(n)。对比把每一对下标都试一遍的双重循环 O(n^2),计数法用「一个值出现 c 次就贡献 c 看一眼」的思路把平方压成了线性
- 空间：O(1) / O(n)，按峰值算。C++ 和 Java 用定长数组 cnt[101],大小只跟值域(1 到 100)有关、与 n 无关,是常数 O(1)。Python 用 Counter 字典,装的是出现过的不同值,最坏情况(全不相同)有 n 个键,这部分是 O(n)。两者都只额外存计数,不存下标对
易错点
面试追问把动画讲成自己的话
追问为什么一个值出现 c 次,贡献的好数对正好是 c 乘以 c 减 1 再除以 2?
追问能不能不用哈希表,改用排序来做?
追问三种语言实现上有什么差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
所有奇数长度子数组的和
LeetCode 1588 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题