Hard

题目描述

给你一个整数数组 nums。

你需要将 nums 中的每个元素移动到两个数组 A 和 B 中的一个，使得 A 和 B 都非空，且 average(A) == average(B)。

如果可以实现这样的分割，返回 true；否则返回 false。

注意：对于数组 arr，average(arr) 是 arr 中所有元素的和除以 arr 的长度。

示例 1：

输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7]，它们的平均值都是 4.5。

示例 2：

输入: nums = [3,1]
输出: false

提示：

  • 1 <= nums.length <= 30
  • 0 <= nums[i] <= 10^4

解题思路

这道题的核心是找到一个子集，使得该子集与剩余元素的平均值相等。

数学推导： 设原数组和为 S，长度为 n，子集 A 的和为 sum_A，长度为 len_A。如果两个子集平均值相等，则： sum_A / len_A = (S - sum_A) / (n - len_A)

化简后得到：sum_A = S * len_A / n

这意味着我们需要找到一个长度为 len_A 的子集，其和等于 S * len_A / n。

解法思路：

  1. 动态规划 + 状态压缩：使用位掩码表示所有可能的子集状态，对于每个可能的子集大小，检查是否存在满足条件的子集
  2. 优化策略：
    • 只需要检查长度为 1 到 n/2 的子集（因为如果长度 k 有解，那么长度 n-k 也必然有解）
    • 使用集合存储每种长度下所有可能的子集和
  3. 剪枝优化：如果 S * len_A 不能被 n 整除，则该长度的子集不可能满足条件

算法复杂度较高但在给定约束下可行，因为 n ≤ 30，最多需要检查 2^30 个状态。

代码实现

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return false;
        
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        // 使用集合存储每个长度下可能的子集和
        vector<unordered_set<int>> dp(n / 2 + 1);
        dp[0].insert(0);
        
        for (int num : nums) {
            for (int len = min(n / 2, (int)dp.size() - 1); len >= 1; len--) {
                for (int prevSum : dp[len - 1]) {
                    dp[len].insert(prevSum + num);
                }
            }
        }
        
        for (int len = 1; len <= n / 2; len++) {
            if (sum * len % n == 0) {
                int target = sum * len / n;
                if (dp[len].count(target)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        n = len(nums)
        if n <= 1:
            return False
        
        total_sum = sum(nums)
        
        # dp[i] 存储长度为 i 的所有可能子集和
        dp = [set() for _ in range(n // 2 + 1)]
        dp[0].add(0)
        
        for num in nums:
            for length in range(min(n // 2, len(dp) - 1), 0, -1):
                for prev_sum in list(dp[length - 1]):
                    dp[length].add(prev_sum + num)
        
        for length in range(1, n // 2 + 1):
            if total_sum * length % n == 0:
                target = total_sum * length // n
                if target in dp[length]:
                    return True
        
        return False

public class Solution {
    public bool SplitArraySameAverage(int[] nums) {
        int n = nums.Length;
        if (n <= 1) return false;
        
        int sum = nums.Sum();
        
        // 使用HashSet存储每个长度下可能的子集和
        var dp = new HashSet<int>[n / 2 + 1];
        for (int i = 0; i <= n / 2; i++) {
            dp[i] = new HashSet<int>();
        }
        dp[0].Add(0);
        
        foreach (int num in nums) {
            for (int len = Math.Min(n / 2, dp.Length - 1); len >= 1; len--) {
                var newSums = new List<int>();
                foreach (int prevSum in dp[len - 1]) {
                    newSums.Add(prevSum + num);
                }
                foreach (int newSum in newSums) {
                    dp[len].Add(newSum);
                }
            }
        }
        
        for (int len = 1; len <= n / 2; len++) {
            if (sum * len % n == 0) {
                int target = sum * len / n;
                if (dp[len].Contains(target)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

var splitArraySameAverage = function(nums) {
    const n = nums.length;
    if (n === 1) return false;
    
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    
    // Check if it's possible to split
    let possible = false;
    for (let i = 1; i < n; i++) {
        if ((totalSum * i) % n === 0) {
            possible = true;
            break;
        }
    }
    if (!possible) return false;
    
    // Use DP to check if we can form subset with required sum and size
    const dp = Array(n).fill(null).map(() => new Set());
    dp[0].add(0);
    
    for (const num of nums) {
        for (let i = Math.min(dp.length - 1, n - 1); i >= 1; i--) {
            for (const sum of dp[i - 1]) {
                dp[i].add(sum + num);
            }
        }
    }
    
    // Check if any valid subset exists
    for (let i = 1; i < n; i++) {
        const targetSum = (totalSum * i) / n;
        if (Number.isInteger(targetSum) && dp[i].has(targetSum)) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × 2^(n/2) × S)n为数组长度，S为数组元素和的范围，需要遍历所有可能的子集
空间复杂度O(n/2 × 2^(n/2))存储每个长度下所有可能的子集和

相关题目