Easy

题目描述

给定一个偶数长度的整数数组 nums。你需要将数组分割成两部分 nums1 和 nums2，满足：

  • nums1.length == nums2.length == nums.length / 2
  • nums1 应包含不同的元素
  • nums2 也应包含不同的元素

如果可以分割数组，返回 true，否则返回 false。

示例 1：

输入：nums = [1,1,2,2,3,4]
输出：true
解释：一种可能的分割方式是 nums1 = [1,2,3]，nums2 = [1,2,4]

示例 2：

输入：nums = [1,1,1,1]
输出：false
解释：唯一可能的分割方式是 nums1 = [1,1]，nums2 = [1,1]。nums1 和 nums2 都不包含不同的元素，因此返回 false

约束条件：

  • 1 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100

解题思路

解题思路

这道题的关键在于理解分割条件：我们需要将数组分成两个等长的子数组，且每个子数组中的元素都必须是不同的。

核心观察： 如果某个数字出现超过 2 次，那么无论如何分割都无法满足条件。这是因为：

  • 数组要分成两个等长部分，每部分包含不同元素
  • 如果某个数字出现 3 次或更多，根据抽屉原理，至少有一个子数组会包含该数字的重复出现

解法分析：

  1. 频率统计法（推荐）： 统计每个元素的出现频率，如果任何元素频率超过 2，则无法分割
  2. 贪心构造法： 实际构造两个集合，但由于只需判断可行性，频率统计更高效

算法步骤：

  1. 遍历数组，统计每个数字的出现次数
  2. 检查是否有任何数字出现次数超过 2
  3. 如果都不超过 2，则可以成功分割（每个数字最多在两个子数组中各出现一次）

时间复杂度 O(n)，空间复杂度 O(k)，其中 k 是不同数字的个数。

代码实现

class Solution {
public:
    bool isPossibleToSplit(vector<int>& nums) {
        unordered_map<int, int> freq;
        
        for (int num : nums) {
            freq[num]++;
            if (freq[num] > 2) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def isPossibleToSplit(self, nums: List[int]) -> bool:
        from collections import Counter
        
        freq = Counter(nums)
        
        for count in freq.values():
            if count > 2:
                return false
        
        return True

public class Solution {
    public bool IsPossibleToSplit(int[] nums) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
            
            if (freq[num] > 2) {
                return false;
            }
        }
        
        return true;
    }
}

var isPossibleToSplit = function(nums) {
    const freq = new Map();
    
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
        if (freq.get(num) > 2) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度时间复杂度空间复杂度
频率统计法O(n)O(k)

其中 n 是数组长度，k 是不同元素的个数（最多为 min(n, 100)）。