好数对的数目 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,3,1,1,3]
- 输出
- 4
- 输入
- nums=[1,1,1,1]
- 输出
- 6
- 输入
- nums=[1,2,3]
- 输出
- 0
最优解：一步一步想明白
- 3记牢一句:每到一个数 x,先把答案加上「前面同值的个数」cnt[x],再让 cnt[x] 自增 1。一遍扫描就能数出全部好数对。下面每帧都在套这句。
- 4先看清画面。上面是数组 nums = [1,2,3,1,1,3],一共 6 个数。右边那张计数表 cnt 现在是空的,它会记下每个值出现过几次。答案 ans 从 0 起步。接下来紫色指针从下标 0 一格一格往右走,每到一个数,就先看计数表里这个值已经有几个,把这么多对好数对加进 ans,再把当前这格登记进表。先从第 0 位开始。
- 5紫色指针落在下标 0,值是 1。去计数表里一查,前面一个 1 都还没出现过,cnt[1] 是 0。没有同值的老位置可配,所以这一格暂时一对也凑不出来,ans 不会变。但它要先把自己登记进表,好让后面再遇到 1 时能和它配。
- 6前面没有同值,这一格给 ans 加 0,答案仍然是 0。这很正常:每个值第一次出现时都配不成对,它的作用是先入表、给后来者当配对对象。
- 7最后把当前这格登记进计数表:值 1 的次数从 0 加到 1,下标 0 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 1,就能把现在这个 0 也算成它的一个配对对象。继续看下一格。
- 8紫色指针落在下标 1,值是 2。去计数表里一查,前面一个 2 都还没出现过,cnt[2] 是 0。没有同值的老位置可配,所以这一格暂时一对也凑不出来,ans 不会变。但它要先把自己登记进表,好让后面再遇到 2 时能和它配。
- 9前面没有同值,这一格给 ans 加 0,答案仍然是 0。这很正常:每个值第一次出现时都配不成对,它的作用是先入表、给后来者当配对对象。
- 10最后把当前这格登记进计数表:值 2 的次数从 0 加到 1,下标 1 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 2,就能把现在这个 1 也算成它的一个配对对象。继续看下一格。
- 11紫色指针落在下标 2,值是 3。去计数表里一查,前面一个 3 都还没出现过,cnt[3] 是 0。没有同值的老位置可配,所以这一格暂时一对也凑不出来,ans 不会变。但它要先把自己登记进表,好让后面再遇到 3 时能和它配。
- 12前面没有同值,这一格给 ans 加 0,答案仍然是 0。这很正常:每个值第一次出现时都配不成对,它的作用是先入表、给后来者当配对对象。
- 13最后把当前这格登记进计数表:值 3 的次数从 0 加到 1,下标 2 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 3,就能把现在这个 2 也算成它的一个配对对象。继续看下一格。
- 14紫色指针落在下标 3,值是 1。去计数表里一查,前面已经出现过 1 个 1,它们的位置是下标 0,现在被标成绿色。这 1 个位置每一个都能和当前的下标 3 配成一组好数对,因为它们值相同、又都排在 3 前面。所以这一格会新增 1 组。
- 15把这新增的 1 组加进答案:ans 从 0 变成 1。绿色那 1 个位置分别和下标 3 组成了好数对。注意我们只在这里加 cnt[1] 这么多,不多不少,正好是前面同值的个数,既不会漏配、也不会重复数同一对。
- 16最后把当前这格登记进计数表:值 1 的次数从 1 加到 2,下标 3 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 1,就能把现在这个 3 也算成它的一个配对对象。继续看下一格。
- 17紫色指针落在下标 4,值是 1。去计数表里一查,前面已经出现过 2 个 1,它们的位置是下标 0、3,现在被标成绿色。这 2 个位置每一个都能和当前的下标 4 配成一组好数对,因为它们值相同、又都排在 4 前面。所以这一格会新增 2 组。
- 18把这新增的 2 组加进答案:ans 从 1 变成 3。绿色那 2 个位置分别和下标 4 组成了好数对。注意我们只在这里加 cnt[1] 这么多,不多不少,正好是前面同值的个数,既不会漏配、也不会重复数同一对。
- 19最后把当前这格登记进计数表:值 1 的次数从 2 加到 3,下标 4 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 1,就能把现在这个 4 也算成它的一个配对对象。继续看下一格。
- 20紫色指针落在下标 5,值是 3。去计数表里一查,前面已经出现过 1 个 3,它们的位置是下标 2,现在被标成绿色。这 1 个位置每一个都能和当前的下标 5 配成一组好数对,因为它们值相同、又都排在 5 前面。所以这一格会新增 1 组。
- 21把这新增的 1 组加进答案:ans 从 3 变成 4。绿色那 1 个位置分别和下标 5 组成了好数对。注意我们只在这里加 cnt[3] 这么多,不多不少,正好是前面同值的个数,既不会漏配、也不会重复数同一对。
- 22最后把当前这格登记进计数表:值 3 的次数从 1 加到 2,下标 5 在数组里标成蓝色表示已经处理完。这样往后再有位置的值是 3,就能把现在这个 5 也算成它的一个配对对象。六个位置全部扫完了。
- 23六个位置都扫完了,回看一遍:值 1 出现在下标 0、3、4 三处,两两配出 (0,3)、(0,4)、(3,4) 共 3 组;值 3 出现在下标 2、5 两处,配出 (2,5) 共 1 组;值 2 只出现一次,配不成对。加起来 3 加 1 等于 4,和题面列出的 4 组好数对完全对上。整道题的窍门就一句:扫描时每到一个数,先用计数表里它前面同值的个数给答案加分,再把自己登记进表,线性时间就数完了。
⚠️ 容易写错的地方
✗ 错：用双重循环把每一对下标 (i, j) 都试一遍,数据一大就慢
✓ 对：一遍扫描加计数表:走到 x 时 ans += cnt[x] 再 cnt[x]++
好数对的本质是「同值的两个位置」,没必要枚举每一对。一个值出现 c 次,它内部的好数对就是从 c 个里挑 2 个,数量固定,用计数边扫边加就行。双重循环是 O(n^2),计数法是 O(n)
✗ 错：把累加和自增的顺序写反,先 cnt[x]++ 再 ans += cnt[x]
✓ 对：必须先 ans += cnt[x](只配前面的),再 cnt[x]++ 登记自己
好数对要求 i 严格小于 j,当前位置只能和「前面」的同值配,不能和自己配。先自增会把自己也算进 cnt[x],导致当前位置和自己凑成一对,多数一组。顺序是先用旧计数累加、再登记
✗ 错：担心同一对会被正反数两次,比如 (0,3) 和 (3,0)
✓ 对：扫描天然只在后来的位置回头配前面的,每对只数一次
我们是从左往右扫,只有走到靠后的下标 j 时才去配前面已入表的下标 i,方向固定是「后配前」,(i, j) 只会在扫到 j 时被数一次,绝不会反过来再数一次,正好契合 i 严格小于 j
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans = 0;
int cnt[101]{};
for (int& x : nums) {
ans += cnt[x]++;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numIdenticalPairs(int[] nums) {
int ans = 0;
int[] cnt = new int[101];
for (int x : nums) {
ans += cnt[x]++;
}
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)。两者都只额外存计数,不存下标对
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 好数对的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么一个值出现 c 次,贡献的好数对正好是 c 乘以 c 减 1 再除以 2?+
这是组合里的「从 c 个中选 2 个」。好数对就是从这 c 个相同值的位置里挑出两个不同位置配成一对,挑法数量是 C(c, 2),也就是 c 乘以 c 减 1 再除以 2。直观理解:第一个位置有 c 种选法,第二个有剩下的 c 减 1 种,但一对里两个位置不分先后,所以要除以 2 去掉重复。比如出现 3 次贡献 3 对,出现 4 次贡献 6 对。所以另一种解法是:先统计每个值的出现次数,再把每个 c 套这个公式加起来,同样得到答案。
能不能不用哈希表,改用排序来做?+
可以。先把数组排序,相同的值就会挨在一起排成一段一段。然后扫一遍,数出每一段相同值的长度 c,套公式 c 乘以 c 减 1 除以 2 累加进答案就行。这样不需要额外的计数表,但排序本身要 O(n log n),比一遍扫描加计数的 O(n) 慢一点。本题值域很小(1 到 100),所以参考解直接用定长数组计数,既是 O(n) 又省心。
三种语言实现上有什么差别?+
Python 用 Counter 字典当计数表,循环里写两行:先 ans 加上 cnt[x],再 cnt[x] 加一,Counter 对没见过的键默认是 0。C++ 和 Java 利用值在 1 到 100 这个限制,直接开长度 101 的整型数组当计数表,用值本身当下标,比哈希更快,而且把两步合成一行 ans += cnt[x]++,后置自增会先返回旧计数累加、再自增,效果和 Python 两行一致。三家都是一遍扫描加计数,差别只在用字典还是定长数组、分两行还是合成 cnt[x]++ 一行。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 好数对的数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。