題目敘述
題目會給定我們一個輸入陣列，要求我們計算好配對的數目有多少個?好配對的定義: 兩個數字相同，但是陣列索引一個在前，一個在後。nums[i] == nums[j] and i < j.
這樣 (i, j) 就稱為一組好配對。
測試範例
Example 1:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Example 2:
Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.
Example 3:
Input: nums = [1,2,3]
Output: 0
約束條件
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
演算法
除了第一直覺，雙層迴圈直接去模擬good pair的生成並且計數以外；這題還有一個高效率的排列組合作法。
對任何一個給定數字num，假如出現k次，那與num有關的good pair數目其實就等於C(k, 2) = C k 取 2 = k * (k-1) / 2
因為任選兩個不同位置的num，都構成一個good pair
所以，只要先做一個字典，統計每個數字的出現次數。
接著，針對每個數字，由C(k, 2)的組合公式計算good pair數目，並且加總，就是最後答案。
程式碼
class Solution:
def numIdenticalPairs(self, nums: List[int]) -> int:
occurrence = Counter( nums )
pair = 0
for num, occ in occurrence.items():
pair += occ * (occ-1) // 2
return pair
複雜度分析
時間複雜度:
O( n ) 建造字典掃描數字耗費O(n)，掃描字典內的數字也耗費O(n)。
空間複雜度:
O( n ) 字典大小最大和陣列一樣長，所佔用空間為O(n)。
關鍵知識點
觀察並且模擬幾個小範例，可以發現good pair背後的原理其實就是n個物品，任選兩個的方法數，可以由排列組合公式計算得到答案。
Reference:
[1] Python sol by iteration - Number of Good Pairs - LeetCode
