题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是找出数组中所有数值相同的数对（好数对）数目，但是数对内的两个值下标不能相同，且交换位置仍视作一个数对。

思路分享

  • 本题就是很基础的枚举题，如果暴力方法就是一个循环遍历数对左侧，另一循环遍历右侧，复杂度为 O(n^2)。

  • 而相对高效的枚举方法为，只用一次循环，遍历到的数字记录到哈希表上各个数值出现的频次，每次遇到一个值，就可以查其左边有多少相同值，也就出现了多少的好数对。

  • 换句话，就是遍历数对的右侧值，并以 O(1) 的复杂度记录其左侧的情况。

  • 枚举的思路以及先记录答案再更新记录的原因可看 【Leetcode Daily】1两数之和

  • 灵神把中间的记录的方式极度地简化，可以借鉴这种思路。

    https://leetcode.cn/problems/number-of-good-pairs/solutions/2974653/mei-ju-you-wei-hu-zuo-pythonjavaccgojsru-7u5v/

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        unordered_map<int,int> rec;
        int res = 0;
        for (const int &i : nums) {
            res += rec[i]++;
            // const auto &it = rec.find(i);
            // if (it!=rec.end()) {
            //     res += it->second;
            //     it->second++;
            // }
            // else {
            //     rec[i]++;
            // }
        }
        return res;
    }
};