LeetCode 1512. 好數對的數目(枚舉右、維護左圖解)

1512. 好數對的數目

題目描述

給你一個整數陣列 nums。如果一組數字 (i, j) 滿足 nums[i] == nums[j] 且 i < j,就可以認為這是一組好數對。

回傳好數對的數目。

範例 1

1
2
3
輸入:nums = [1,2,3,1,1,3]
輸出:4
解釋:有 4 組好數對,分別是 (0,3), (0,4), (3,4), (2,5),下標從 0 開始

範例 2

1
2
3
輸入:nums = [1,1,1,1]
輸出:6
解釋:陣列中的每組數字都是好數對

範例 3

1
2
輸入:nums = [1,2,3]
輸出:0

限制

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」,題解連結。圖解與步驟說明為自行補充。

前置知識:枚舉右,維護左

題目要數「兩個位置」的組合 (i, j),直接枚舉兩個位置要 O(n²)。常見的化簡方式是只枚舉其中一個位置,另一個位置用資料結構一次問出來:

  • 把 j 當成「右邊那個數」,從左到右枚舉。
  • 枚舉到 j 時,左邊(也就是 i < j 的所有位置)已經看過了,我們把左邊的資訊記在一個計數表裡。
  • 計數表回答「左邊有幾個數等於 nums[j]」,這個數量就是以 j 為右端點的好數對個數。

這個套路叫「枚舉右,維護左」。要維護的資訊是「每個值出現過幾次」,用陣列或哈希表都可以。

思路

先看暴力

雙重迴圈,枚舉 j,再往左數有幾個 nums[i] == nums[j]:

1
2
3
4
5
6
int ans = 0;
for (int j = 0; j < nums.length; j++) {
for (int i = 0; i < j; i++) {
if (nums[i] == nums[j]) ans++;
}
}

時間 O(n²)。這題 n ≤ 100 所以能過,但「往左數有幾個」這件事其實每次都在重複計算。

優化:邊走邊記

以 nums = [1, 1, 2, 1] 為例:

  1. 走到 nums[0] = 1:左邊沒有數字,貢獻 0。
  2. 走到 nums[1] = 1:左邊有 1 個 1,找到好數對 (0, 1),貢獻 1。
  3. 走到 nums[2] = 2:左邊沒有 2,貢獻 0。
  4. 走到 nums[3] = 1:左邊有 2 個 1,找到 (0, 3) 和 (1, 3),貢獻 2。

答案是 0 + 1 + 0 + 2 = 3。

一般地,走到元素 x 時,把答案加上「之前遍歷過的 x 的個數」,然後把 x 的個數加一。

演算法:

  1. 準備一個計數表 cnt,記錄每個值之前出現過幾次,一開始全是 0。
  2. 從左到右遍歷 nums,設目前的數是 x(也就是 nums[j])。
  3. 先 ans += cnt[x]。
  4. 再把 cnt[x] 加一。
  5. 遍歷結束,ans 就是答案。

步驟 3 和 4 的順序不能換,原因放在文末「答疑」,圖解裡也可以用切換按鈕親自試。

方法一:陣列計數

思路

限制說 1 <= nums[i] <= 100,值域很小,直接開一個長度 101 的 int 陣列,cnt[x] 就是「之前遍歷過的 x 的個數」,下標就是值本身,不需要任何轉換。

圖解(可互動)

用範例 1 nums = [1,2,3,1,1,3]。每個 j 會走兩步:先 ans += cnt[x](綠色格是左邊跟 x 相同的數,就是新找到的好數對的 i),再 cnt[x]++。按上方的按鈕可以切到「錯誤順序」,看看先計數會多算什麼。

執行順序:
nums = [1,2,3,1,1,3]
x = nums[j]—
之前出現過幾次—
ans(好數對)0

解法(灵茶山艾府)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int numIdenticalPairs(int[] nums) {
int ans = 0;
int[] cnt = new int[101];
for (int x : nums) { // x = nums[j]
// 此時 cnt[x] 表示之前遍歷過的 x 的個數,加到 ans 中
// 如果先執行 cnt[x]++,再執行 ans += cnt[x],就把 i=j 這種情況也統計進來了,算出的答案會偏大
ans += cnt[x];
cnt[x]++;
}
return ans;
}
}

複雜度分析

  • 時間複雜度:O(n),其中 n 是 nums 的長度。每個元素只處理一次。
  • 空間複雜度:題解寫 O(n)。更精確地說,陣列大小只跟值域有關,這題固定 101,所以是 O(U)(U 為值域大小,這裡是常數)。

方法二:哈希表計數

思路

如果值域很大(例如 nums[i] 到 10⁹),開不了那麼大的陣列,就改用哈希表 Map<Integer, Integer>,只記錄出現過的值。

和陣列版唯一的差別是「讀」與「寫」的寫法:

  • 讀:cnt.getOrDefault(x, 0),沒出現過的值當作 0 次。
  • 寫:cnt.put(x, c + 1)。

這裡先把 c = getOrDefault(x, 0) 存起來,用一次拿到的 c 同時完成「加到答案」與「更新次數」,不用查兩次表。

圖解(可互動)

同樣的範例,注意右邊的 Map 一開始是空的,值第一次出現時才會新增一筆(例如 j = 0 時還沒有 1,getOrDefault 回傳 0)。

執行順序:
nums = [1,2,3,1,1,3]
x = nums[j]—
之前出現過幾次—
ans(好數對)0

解法(灵茶山艾府)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int numIdenticalPairs(int[] nums) {
int ans = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
int c = cnt.getOrDefault(x, 0);
ans += c;
cnt.put(x, c + 1);
}
return ans;
}
}

複雜度分析

  • 時間複雜度:O(n),其中 n 是 nums 的長度。哈希表讀寫平均 O(1)。
  • 空間複雜度:O(n),最壞情況所有數都不同,Map 要存 n 筆。

答疑

問:為什麼代碼要先更新答案,再更新 cnt?

答:題目要求 i < j。如果先更新 cnt,再更新答案,就會把 nums[j] 自己也統計進來,相當於把 i = j 的情況也當成好數對,答案會偏大。以範例 1 為例,先計數的錯誤版本會算出 10,而正確答案是 4。(措辭為自行改寫)

相似題目

題解提到,更多相似題目可以看作者整理的資料結構題單中的「§0.1 枚舉右,維護左」。題單沒有給網址,這裡不放連結。


LeetCode 1512. 好數對的數目(枚舉右、維護左圖解)
https://shengshengyang.github.io/2026/11/06/leetcode-1512-number-of-good-pairs/
作者
Dean Yang
發布於
2026年11月6日
許可協議