题目描述
思路解析动画文字版
记牢一句:每到一个数 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题