1512.Number of Good Pairs

Tags: Easy Array Hash Table Math

Links: https://leetcode.com/problems/number-of-good-pairs/

---

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

---

看数据范围最直接的想法肯定是暴力求解即可。时间复杂度$O(n^2)$。

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] == nums[j]) ++cnt;
            }
        }

        return cnt;
    }
};

但是本题存在$O(n)$的解法，我们可以统计某一数字出现的次数，数对其实就是从次数中选择出任意两个即可，时间复杂度$O(n)$，注意，出现次数不小于2.

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int cnt = 0;
        unordered_map<int, int> um;
        for (auto & e : nums) ++um[e];
        for (auto & e : um) {
            if (e.second > 1) cnt += (long long)e.second * (e.second - 1) / 2;
        }

        return cnt;
    }
};

另外注意到数据范围不超过100，所以可以开一个长度为101的数组即可，来代替哈希表。

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int cnt = 0;
        vector<int> count(101, 0);
        for (auto & e : nums) ++count[e];
        for (auto & e : count) {
            if (e > 1) cnt += (long long)e * (e - 1) / 2;
        }

        return cnt;
    }
};