Leetcode 1512. Number of Good Pairs

給定一個array名叫nums, 如果nums[i] == nums[j] 而且索引 i < j,我們稱為好的組合,計算出總共有幾組好的組合。

想法

(1)暴力法

我們使用兩個for迴圈去遍歷所有組合。

程式碼:

def numIdenticalPairs(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if(nums[i]==nums[j]):
                    ans+=1
        return ans

(2)數學方法

我們透過歸納可以得知以下結果。
[1] = 0
[1,1] = 1
[1,1,1] = 3
[1,1,1,1] = 6
[1,1,1,1,1] = 10
得到公式 n = f(n-1)+n-1 所以我們可以直接計算每個元素在array中重複的次數,則可以得到答案。

程式碼:

def numIdenticalPairs(self, nums: List[int]) -> int:
        dict2 = {}
        def f(n):
            if(n in dict2):
                return dict2[n]
            elif(n==2):
                return 1
            elif(n<2):
                return 0
            else:
                dict2[n] = n-1+f(n-1)
                return dict2[n]
        dict1 = {}
        for i in nums:
            dict1[i] = dict1.get(i,0)+1
        ans = 0
        for i in dict1:
            if(dict1[i] not in dict2):
                dict2[dict1[i]] = f(dict1[i])
            ans+=dict2[dict1[i]]
        return ans