Easy

题目描述

给你一个整数数组 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

解题思路

解题思路

这道题的核心思想是：要将数组分成相等的对，每个数字的出现次数必须是偶数。

分析过程

  1. 理解题意：我们需要将数组中的元素两两配对，且每一对中的两个元素必须相等。

  2. 关键观察：对于任何数字 x，如果它在数组中出现了奇数次，那么必然有一个 x 无法找到配对，因此无法满足题目要求。

  3. 解法思路：

    • 哈希表统计法：统计每个数字的出现次数，检查是否所有数字的出现次数都是偶数
    • 位运算优化法：利用异或运算的性质，相同数字异或结果为0，最终结果为0说明所有数字都出现偶数次

推荐解法

推荐使用位运算解法，因为它空间复杂度更优且代码更简洁。异或运算的特性是相同数字异或为0，不同数字异或保持原值。如果所有数字都出现偶数次，那么最终异或结果必定为0。

代码实现

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        return xorSum == 0;
    }
};

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        xor_sum = 0
        for num in nums:
            xor_sum ^= num
        return xor_sum == 0

public class Solution {
    public bool DivideArray(int[] nums) {
        int xorSum = 0;
        foreach (int num in nums) {
            xorSum ^= num;
        }
        return xorSum == 0;
    }
}

var divideArray = function(nums) {
    const count = {};
    
    for (let num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    
    for (let freq of Object.values(count)) {
        if (freq % 2 !== 0) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型位运算解法哈希表解法
时间复杂度O(n)O(n)
空间复杂度O(1)O(k)，k为不同数字的个数

相关题目