Leetcode Weekly Contest 197 - The Number of Good Pairs

LINK

Level : Easy

Problem

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.

Solution

class Solution {
public:
    
    int count(int n){
        int ans = (n + 1)*(n/2);
        if(n%2 != 0){
            ans += n/2 + 1;
        }
        return ans;
    }
    
    int numIdenticalPairs(vector<int>& nums) {
        int n=0;
        unordered_map<int, int> list;
        for (size_t i = 0; i < nums.size(); ++i){
            auto it = list.find(nums[i]);
            if(it != list.end()){
                ++(it->second);    
            }else{
                list.insert(pair<int,int>(nums[i],0));
            }
            
        }
        for (auto it : list){
            if(it.second > 0){
                n += count(it.second);
            }
        }
        return n;
    }
};

Time copmlexity: O(n)