Skip to content

Latest commit

 

History

History
 
 

1512. Number of Good Pairs

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

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.

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 <= 100
  • 1 <= nums[i] <= 100

Related Topics:
Array, Hash Table, Math

Solution 1. Brute force

// OJ: https://leetcode.com/problems/number-of-good-pairs/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) ans += nums[i] == nums[j];
        }
        return ans;
    }
};

Solution 2. Count

// OJ: https://leetcode.com/problems/number-of-good-pairs/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> m;
        int ans = 0;
        for (int n : nums) ans += m[n]++;
        return ans;
    }
};