LeetCode 1512. 好數對的數目(枚舉右、維護左圖解)
1512. 好數對的數目
題目描述
給你一個整數陣列 nums。如果一組數字 (i, j) 滿足 nums[i] == nums[j] 且 i < j,就可以認為這是一組好數對。
回傳好數對的數目。
範例 1
1 | |
範例 2
1 | |
範例 3
1 | |
限制
1 <= nums.length <= 1001 <= nums[i] <= 100
本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」,題解連結。圖解與步驟說明為自行補充。
前置知識:枚舉右,維護左
題目要數「兩個位置」的組合 (i, j),直接枚舉兩個位置要 O(n²)。常見的化簡方式是只枚舉其中一個位置,另一個位置用資料結構一次問出來:
- 把
j當成「右邊那個數」,從左到右枚舉。 - 枚舉到
j時,左邊(也就是i < j的所有位置)已經看過了,我們把左邊的資訊記在一個計數表裡。 - 計數表回答「左邊有幾個數等於
nums[j]」,這個數量就是以j為右端點的好數對個數。
這個套路叫「枚舉右,維護左」。要維護的資訊是「每個值出現過幾次」,用陣列或哈希表都可以。
思路
先看暴力
雙重迴圈,枚舉 j,再往左數有幾個 nums[i] == nums[j]:
1 | |
時間 O(n²)。這題 n ≤ 100 所以能過,但「往左數有幾個」這件事其實每次都在重複計算。
優化:邊走邊記
以 nums = [1, 1, 2, 1] 為例:
- 走到
nums[0] = 1:左邊沒有數字,貢獻 0。 - 走到
nums[1] = 1:左邊有 1 個 1,找到好數對(0, 1),貢獻 1。 - 走到
nums[2] = 2:左邊沒有 2,貢獻 0。 - 走到
nums[3] = 1:左邊有 2 個 1,找到(0, 3)和(1, 3),貢獻 2。
答案是 0 + 1 + 0 + 2 = 3。
一般地,走到元素 x 時,把答案加上「之前遍歷過的 x 的個數」,然後把 x 的個數加一。
演算法:
- 準備一個計數表
cnt,記錄每個值之前出現過幾次,一開始全是 0。 - 從左到右遍歷
nums,設目前的數是x(也就是nums[j])。 - 先
ans += cnt[x]。 - 再把
cnt[x]加一。 - 遍歷結束,
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]++。按上方的按鈕可以切到「錯誤順序」,看看先計數會多算什麼。
解法(灵茶山艾府)
1 | |
複雜度分析
- 時間複雜度: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)。
解法(灵茶山艾府)
1 | |
複雜度分析
- 時間複雜度:O(n),其中 n 是
nums的長度。哈希表讀寫平均 O(1)。 - 空間複雜度:O(n),最壞情況所有數都不同,Map 要存 n 筆。
答疑
問:為什麼代碼要先更新答案,再更新 cnt?
答:題目要求 i < j。如果先更新 cnt,再更新答案,就會把 nums[j] 自己也統計進來,相當於把 i = j 的情況也當成好數對,答案會偏大。以範例 1 為例,先計數的錯誤版本會算出 10,而正確答案是 4。(措辭為自行改寫)
相似題目
題解提到,更多相似題目可以看作者整理的資料結構題單中的「§0.1 枚舉右,維護左」。題單沒有給網址,這裡不放連結。