1512. 好数对的数目（vector+unordered_map）

古城微笑少年丶 2022-12-07 15:27 97阅读 0赞

# 1.题目描述 #

给你一个整数数组 nums 。

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

返回好数对的数目。

**示例 1：**

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

# 2.暴力求解 #

#include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;
    
    /*
    直接暴力求解：
    执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
    内存消耗：7 MB, 在所有 C++ 提交中击败了92.01%的用户
    时间复杂度：O(n^2)
    空间复杂度：O(1)
    */
    int numIdenticalPairs(vector<int> &nums)
    {
        int i, j;
        int ans = 0;
        for (i = 0; i < nums.size(); i++)
        {
            for (j = i + 1; j < nums.size(); j++)
            {
                if (nums[i] == nums[j])
                {
                    ans++;
                }
            }
        }
        return ans;
    }
    
    
    int main()
    {
        int nums[6] = {1, 2, 3, 1, 1, 3};
        vector<int> vec(nums, nums + 6);
        int ans = numIdenticalPairs(vec);
        cout << ans << endl;
        return 0;
    }

# 3.hashmap组合计数 #

![20200916194415416.png][]

#include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;
    
    /*
    hashmap：
    执行用时：4 ms, 在所有 C++ 提交中击败了51.48%的用户
    内存消耗：7.2 MB, 在所有 C++ 提交中击败了40.48%的用户
    时间复杂度：O(n)。
    空间复杂度：O(n)，即哈希表使用到的辅助空间的空间代价。
    */
    
    int numIdenticalPairs(vector<int> &nums)
    {
        unordered_map<int, int> map;
        for (int num : nums)
        {
            ++map[num];
        }
    
        int ans = 0;
        for (const auto &[k, v] : map)
        {
            ans += v * (v - 1) / 2;
        }
    
        return ans;
    }
    
    int main()
    {
        int nums[6] = {1, 2, 3, 1, 1, 3};
        vector<int> vec(nums, nums + 6);
        int ans = numIdenticalPairs(vec);
        cout << ans << endl;
        return 0;
    }

[20200916194415416.png]: /images/20221123/409c7f64b9fa4f19846abcf15b4f4010.png