数组的均值分割

题目

805. 数组的均值分割

---

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

题解

方法一：

思路

折半搜索解决的经典问题。

长度为n=40以内的数组arr选取一些元素使得和为x。可以二进制枚举前n/2个元素的组合，将每个组合的和存入哈希表，然后二进制枚举后n/2个元素的组合，当 x-组合值 在哈希表中存在便找到了两个组合。时间复杂度$O(2^{\frac{n}{2}})$

数组中的值比较小还可以用01背包解决。

这里A数组的平均值和B数组的平均值相等，其实也和整个数组的平均值相等。

sum(a) * len(b) = sum(b) * len(a)
sum(a) * (n-len(a) ) = sum(b)*len(a)
sum(a) * n = (sum(a) + sum(b))*len(a)
sum(a)/len(a) = (sum(a)+sum(b))/n

然后让数组中每个值减去平均值，数组的平均值变为0，只需找到一个子序列的平均值为0那么剩余的数的平均值也是0，平均值为0就是和为0.

这个题对于折半搜索其实并不难理解，但是比较棘手的地方就是两个集合不能有一个是空集合。设我们在左半数组选的数的集合是X，右半数组选的数的集合是Y，

X共有三种状态在左半数组中一个都不选X0，选一部分X1，全选X2。

Y同理有Y0，Y1，Y2。

X和Y中的数将移入到A数组，剩余没选的数移入B数组，A和B不能为空，所以X和Y不能全为空或全选，即X0Y0，X2Y2的组合是不合法的。

所以X和Y的所有状态的组合中只有3 * 3 - 2 = 7种是合法的。

只需判断7钟组合是不是存在和为0即可。

首先我们可以预处理出左半和lsum，右半和rsum。

由于lsum+rsum=0, 所以当lsum=0是rsum也=0，这样就判断完两种状态X2Y0，X0Y2.

二进制枚举左半数组X1状态的子集，可以判断X1Y0，X1Y2是不是和为0

同理右半数组判断X0Y1，X2Y1是不是和为0

最后可以在右半枚举Y1时，查询左半枚举X1的哈希表判断最后一种组合X1Y1和为0的情况。

代码

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return false;
        int s = accumulate(nums.begin(), nums.end(), 0);
        for (auto& i:nums) i = i*n-s;
        int s1 = accumulate(nums.begin(), nums.begin()+n/2, 0), s2 = -s1;
        if (s1 == 0) return true;
        unordered_map<int,int> mp;
        for (int i=1; i+1<1<<n/2; i++) {
            int cnt = 0;
            for (int j=0; j<n/2; j++) {
                if (i>>j&1) cnt += nums[j];
            }
            if (cnt == 0 || cnt + s2 == 0) return true;
            mp[cnt]++;
        }
        for (int i=1; i+1<1<<n-n/2; i++) {
            int cnt = 0;
            for (int j=0; j<n-n/2; j++) {
                if (i>>j&1) cnt += nums[j+n/2];
            }
            if (cnt == 0 || cnt + s1 == 0 || mp.count(-cnt)) return true;
        }
        return false;
    }
};