【2022-11-14每日一题】805. 数组的均值分割[Hard]

2022-11-14每日一题：805. 数组的均值分割

难度：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] <= 104

方法一：折半查找

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

• 题解一
• 题解二

func splitArraySameAverage(nums []int) bool {
    n := len(nums)
    if n == 1 { // 不符合A, B都有元素
        return false
    }
    
    // 求和
    sum := 0
    for _, v := range nums {
        sum += v
    }
    // 预处理数组
    for i, v := range nums {
        nums[i] = v * n - sum
    }
    
    m := n >> 1 // 相当于 n/2
    left := map[int]bool{}
  	// 左侧处理
    for i := 1; i < 1<<m; i++ {
        total := 0
        for j, v := range nums {
            if i>>j&1 > 0 {
                total += v
            }
        }
        if total == 0 {
            return true
        }
        left[total] = true
    }
    
    // 右半部分处理
    rsum := 0
    for _, v := range nums[m:] {
        rsum += v
    }
    for i := 1; i < 1<<(n-m); i++ {
        total := 0
        for j, v := range nums[m:] {
            if i>>j&1 > 0 {
                total += v
            }
        }
        // rsum != total 等价于 (i != (1<<(n-m))-1
        if total == 0 || rsum != total && left[-total] {
            return true
        }
    }
    return false
}

复杂度分析

方法二：动态规划

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func splitArraySameAverage(nums []int) bool {
    sum := 0
    for _, x := range nums {
        sum += x
    }

    n := len(nums)
    m := n >> 1 // n / 2
    isPossible := false
    for i := 1; i <= m; i++ {
        if sum*i%n == 0 {
            isPossible = true
            break
        }
    }
    if !isPossible {
        return false
    }

    dp := make([]map[int]bool, m+1)
    for i := range dp {
        dp[i] = map[int]bool{}
    }
    dp[0][0] = true
    for _, num := range nums {
        for i := m; i >= 1; i-- {
            for x := range dp[i-1] {
                curr := x + num
                if curr*n == sum*i {
                    return true
                }
                dp[i][curr] = true
            }
        }
    }
    return false
}

复杂度分析

LeetCode题库地址

• https://leetcode.cn/problems/split-array-with-same-average