好数对的数目 图解题解

同值又前后成对的下标，一共几组

给你一个数组 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 组。

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 ans

C++

#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;
    }
}