# LeetCode 1512. Number of Good Pairs
[LeetCode 1512. Number of Good Pairs](leetcode_url) (難度 通過率)
<!--
(<font color=#00AF9B>Easy</font> 53.8%)
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
-->

- 限制 :

<ul>
<li><code></code></li>
<li><code></code></li>
<li><code></code></li>
</ul>

- Solution A
這題有點困難，但又不太困難(?
這題主要問的是有幾組 pair 在這群數列當中。
解法一是直接用暴力法一個一個看，找到所有的 pair 即為所求。慢但有效。
- 時間複雜度: $O(n^2)$
- 空間複雜度: $O(1)$

- 程式碼

    class Solution {
    public:
        int numIdenticalPairs(vector<int>& nums) {
            int result = 0;
            for (int i = 0; i < nums.size(); i++) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[i] == nums[j]) {
                        result += 1;
                    }
                }
            }
            return result;
        }
    };

- Solution B
第二種解題方式是利用 unordered_map 紀錄出現的次數，而出現頻率和成對次數有絕對的關聯:
1. 出現 1 次會有 0 個 pair
2. 出現 2 次會有 0 + 1 個 pair
3. 出現 3 次會有 1 + 2 個 pair
4. 出現 4 次會有 3 + 3 個 pair ，以此類推

所以找到這個規律可以消掉一個迴圈來加快速度。但缺點就是要建一個 unordered_map 來儲存這些資訊。
- 時間複雜度: $O(n)$
- 空間複雜度: $O(n)$

- 程式碼

    class Solution {
    public:
        int numIdenticalPairs(vector<int>& nums) {
            int ans = 0;
            unordered_map<int, int> cnt;
            for (int& x : nums) {
                ans += cnt[x]++;
            }
            return ans;
        }
    };