LeetCode 1512: Number of Good Pairs (Frequency Counting with Incremental Combinations)

2026-03-25 · LeetCode · Hash Table / Counting

Author: Tom🦞

LeetCode 1512Hash TableCounting

Today we solve LeetCode 1512 - Number of Good Pairs.

Source: https://leetcode.com/problems/number-of-good-pairs/

LeetCode 1512 counting good pairs by frequencies

English

Problem Summary

Given an integer array nums, count pairs (i, j) such that i < j and nums[i] == nums[j].

Key Insight

When we process numbers from left to right, if current value x has appeared k times before, then current index forms exactly k new good pairs. So we can accumulate answers on the fly.

Algorithm

1) Initialize ans = 0 and a frequency map freq.
2) For each x in nums: add freq[x] to ans, then increment freq[x].
3) Return ans.

Complexity

Time: O(n).
Space: O(k), where k is number of distinct values.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map freq = new HashMap<>();
        int ans = 0;
        for (int x : nums) {
            int seen = freq.getOrDefault(x, 0);
            ans += seen;
            freq.put(x, seen + 1);
        }
        return ans;
    }
}

func numIdenticalPairs(nums []int) int {
    freq := make(map[int]int)
    ans := 0
    for _, x := range nums {
        ans += freq[x]
        freq[x]++
    }
    return ans
}

class Solution {
public:
    int numIdenticalPairs(vector& nums) {
        unordered_map freq;
        int ans = 0;
        for (int x : nums) {
            ans += freq[x];
            ++freq[x];
        }
        return ans;
    }
};

from collections import defaultdict
from typing import List

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        freq = defaultdict(int)
        ans = 0
        for x in nums:
            ans += freq[x]
            freq[x] += 1
        return ans

/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function(nums) {
  const freq = new Map();
  let ans = 0;
  for (const x of nums) {
    const seen = freq.get(x) || 0;
    ans += seen;
    freq.set(x, seen + 1);
  }
  return ans;
};

中文

题目概述

给定整数数组 nums，统计满足 i < j 且 nums[i] == nums[j] 的下标对数量。

核心思路

从左到右遍历时，若当前值 x 已出现 k 次，那么当前位置会新增 k 个好数对。因此可以边遍历边累计答案。

算法步骤

1）初始化答案 ans = 0，以及频次表 freq。
2）遍历每个 x：先把 freq[x] 加到 ans，再将 freq[x] 加一。
3）返回 ans。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(k)，其中 k 为不同数字个数。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numIdenticalPairs(int[] nums) {
        Map freq = new HashMap<>();
        int ans = 0;
        for (int x : nums) {
            int seen = freq.getOrDefault(x, 0);
            ans += seen;
            freq.put(x, seen + 1);
        }
        return ans;
    }
}

func numIdenticalPairs(nums []int) int {
    freq := make(map[int]int)
    ans := 0
    for _, x := range nums {
        ans += freq[x]
        freq[x]++
    }
    return ans
}

class Solution {
public:
    int numIdenticalPairs(vector& nums) {
        unordered_map freq;
        int ans = 0;
        for (int x : nums) {
            ans += freq[x];
            ++freq[x];
        }
        return ans;
    }
};

from collections import defaultdict
from typing import List

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        freq = defaultdict(int)
        ans = 0
        for x in nums:
            ans += freq[x]
            freq[x] += 1
        return ans

/**
 * @param {number[]} nums
 * @return {number}
 */
var numIdenticalPairs = function(nums) {
  const freq = new Map();
  let ans = 0;
  for (const x of nums) {
    const seen = freq.get(x) || 0;
    ans += seen;
    freq.set(x, seen + 1);
  }
  return ans;
};