---
# System prepended metadata

title: LeetCode 1512. Number of Good Pairs

---

# 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)$

- 程式碼
    ```c++=
    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)$

- 程式碼
    ```c++=
    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;
        }
    };
    ```
