题目描述

给你一个整数数组 nums。

如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j，就可以认为这是一组 好数对。

返回好数对的数目。

样例

输入：nums = [1,2,3,1,1,3]
输出：4
解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始。

输入：nums = [1,1,1,1]
输出：6
解释：数组中的每组数字都是好数对。

输入：nums = [1,2,3]
输出：0

限制

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

算法

(哈希表) $O(n)$

1. 从前往后遍历数组，对于 nums[i]，如果前边出现了 x 次，则答案累加 x。
2. 用一个哈希表统计数字的出现次数。

时间复杂度

• 遍历一次数组，哈希表的操作时间复杂度为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间记录数字的出现次数。

C++ 代码

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int, int> mp;
        int ans = 0;

        for (int x : nums) {
            ans += mp[x];
            mp[x]++;
        }

        return ans;
    }
};