2206-将数组划分成相等数对

给你一个整数数组 nums ，它包含 2 * n 个整数。

你需要将 nums 划分成 n 个数对，满足：

• 每个元素 只属于一个 数对。
• 同一数对中的元素 相等 。

如果可以将 nums 划分成 n 个数对，请你返回 true ，否则返回 false 。

示例 1：

**输入：** nums = [3,2,3,2,2,2]
**输出：** true
**解释：**
nums 中总共有 6 个元素，所以它们应该被划分成 6 / 2 = 3 个数对。
nums 可以划分成 (2, 2) ，(3, 3) 和 (2, 2) ，满足所有要求。

示例 2：

**输入：** nums = [1,2,3,4]
**输出：** false
**解释：**
无法将 nums 划分成 4 / 2 = 2 个数对且满足所有要求。

提示：

• nums.length == 2 * n
• 1 <= n <= 500
• 1 <= nums[i] <= 500

方法一：哈希表

思路与算法

对于数组 nums，它「能被划分成 n 个相等数对」等价于「所有元素的出现次数均为偶数」。因此，我们只需要判断数组 nums 的每个元素的出现次数是否为偶数即可。

具体地，我们遍历数组 nums，并用哈希表 freq 统计每个元素的出现次数。最后，我们遍历 freq 的所有值检查它们是否均为偶数。如果是，则说明该数组可以被划分成 n 个相等数对，我们返回 true；反之则不行，我们返回 false。

代码

[sol1-C++]

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        unordered_map<int, int> freq;   // 元素出现次数哈希表
        for (int num: nums) {
            ++freq[num];
        }
        return all_of(freq.begin(), freq.end(), [](auto p) { return p.second % 2 == 0; });
    }
};

[sol1-Python3]

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        freq = Counter(nums)   # 元素出现次数哈希表
        return all(f % 2 == 0 for f in freq.values())

复杂度分析

• 时间复杂度：O(n)，其中 n 为 nums 可以拆分的数对个数。即为统计数组中每个数字出现次数并判断是否可以按要求划分的时间复杂度。

• 空间复杂度：O(n)，即为出现次数哈希表的空间开销。