[数据结构与算法]LeetCode 2206. Divide Array Into Equal Pairs【数组/哈希】简单

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

• Each element belongs to exactly one pair.
• The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

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

题意：给出一个长为 $2\times n$ 的整数数组 nums ，需要将 nums 划分成 $n$ 个数对，满足：每个元素 只属于一个 数对；同一数对中的元素 相等 。如果可以将 nums 划分成 $n$ 个数对，返回 true ，否则返回 false 。

解法 哈希计数

这就是道计数题，我们对 $[1,500]$ 范围内的任一数字 $x$ ，计算 nums[] 中值等于 $x$ 的元素数目，当且仅当其数目为偶数时，具有相等值的元素 $x$ 可以完全分成多个数对。具体实现上，可以使用整型数组进行哈希计数，然后判断每种元素是否为偶数个：

// Java Version
class Solution {
    public boolean divideArray(int[] nums) {
        int[] cnt = new int[510];
        for (int v : nums) ++cnt[v];
        for (int i = 1; i <= 500; ++i)
            if ((cnt[i] & 1) == 1) return false;
        return true;
    }
}
// 执行用时：1 ms, 在所有 Java 提交中击败了99.93% 的用户
// 内存消耗：41.1 MB, 在所有 Java 提交中击败了95.66% 的用户