[LeetCode]#1512. Number of Good Pairs

Environment: Python 3.7

Key technique: {}

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

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.

Analysis:

1. Find number showing frequency in nums.
2. Use formula n(n-1)/2 to calculate pairs.
3. Return all pair result.

Solution:

class Solution:
    def numIdenticalPairs(self, nums):
        f={}
        ans=0
        for num in nums:
            if not num in f:
                f[num]=0
            f[num]+=1
        
        for num in f:
            n=f[num]
            ans+=(n*(n-1)//2)
            
        return ans

Submissions:

Reference:

Python - Faster than 100% of Submission - LeetCode Discuss

http://mathforum.org/library/drmath/view/61212.html