[leetcode每日一题]11.14

​​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] <= 104​​

Solution

可以用折半查找空间换时间，因为枚举2^30个状态可能有点多，而2^15个状态就刚刚好。在枚举状态时，又可以用int的位来存储nums的每一个位置。因此，将数组分成前后2段，枚举前一段的所有可能和，并存储到一个set里。再遍历后半段，如果后半段的某个和等于前半段某个和的相反数，则返回true。

注1：可以通过将每个元素减去平均值，使整个数组变成零和的。考虑到平均值可能不为整数，可以将每个元素先乘以数组长度，使得平均值肯定是整数。

注2：判断数组长度为1的情况，返回false。

注3：如果遍历到某个和为0，则返回true。

注4：需要单独判断前后两段和为相反数的情况是不是取了数组的所有元素的和，因为这样也无法分为两部分。具体来说可以存储后半段的和，如果最后遍历的和等于后半段的和，则不能算。因为如果此时没有取遍后半段所有元素，那么没取的元素的和一定为0，可以通过注3判断出来。

代码(C++)

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int s = accumulate(nums.begin(), nums.end(), 0);
        int l = nums.size();
        if(l==1)return false;
        for(int i=0;i<l;i++){
            nums[i] *= l;
            nums[i] -= s;
        }
        int m = (l+1)/2;
        unordered_set<int> left;
        for(int i=1;i<1<<m;i++){
            int cur = 0;
            for(int j=0;j<m;j++){
                if(i>>j&1)cur+=nums[j];
            }
            if(cur == 0)return true;
            left.emplace(cur);
        }
        int r = accumulate(nums.begin()+m, nums.end(), 0);
        for(int i=1;i<1<<(l-m);i++){
            int cur = 0;
            for(int j=0;j<m;j++){
                if(i>>j&1)cur+=nums[j+m];
            }
            if(left.count(-cur)&&cur!=r||cur==0) return true;
        }
        return false;
    }
};

不过也可以转化成背包问题用dp做，存储状态的数据结构为vector<unordered_set<int>>。