力扣(LeetCode)805. 数组的均值分割(C++)

状态压缩+折半搜索

分析均值分割的性质，
设分割后 $A$ 数组长度为 $k$ ，那么 $B$ 数组长度为 $n-k$ ，$A$ 和 $B$ 平均值相等，有 $\frac{su{m}_A}{k}=\frac{su{m}_B}{n-k}$。除法需要转换浮点数，有精度问题。为了避免精度问题，整理上式。
整理，得 $①su{m}_A\times (n-k)=su{m}_B\times k$。
设 $nums$ 所有数之和为 $sum$ , 有 $②sum=su{m}_A+su{m}_B$
$①②$联立，得
$③su{m}_A\times n=sum\times k$
由于$①<=>③$，问题转化为，求与$num$均值相等的$A$。$A$ 是 $nums$ 的子数组。原问题：求$nums$的均值分割数组 $A$、$B$。

归一化处理，令 $nums$ 的每一个数 $x=nx-sum$，避免精度处理。归一化改变 $nums$ 的平均值，为 $0$。问题转化为，求均值为 $0$ 的 $A$ 。

用状态压缩表示 $A$ 选取了 $nums$ 的哪些数，$1$ 表示选，$0$ 表示不选。$nums$ 最大长度 $30$ ，可知一共 $2^{30}$ 种状态，$TLE$ 。

于是折半查找，把 $nums$ 均分为$left$ 、$right$ 两半，对两半分别状态压缩，求均值等于 $0$ 的 $A$ 。设 $A$ 的某状态，总和为 $total$ ，如果 $B$ 中存在某状态，总和为 $-total$，两个状态之和的均值为 $0$ ，这也是一个可行解 。上述过程，和直接查找整个 $nums$ 是等价的。但是状态数量缩减为 $2\times 2^{15}$

要注意，在 $right$ 中不能选取所有元素，否则相当于选择了整个 $nums$ 作为 $A$ 数组，不符合题意。

代码展示

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size(), m = n/2;//n是nums的长度,m是左子数组A的长度
        if(0==m) return false;//单元素数组//不可分割
        int sum = accumulate(nums.begin(),nums.end(),0);
        for(auto &x:nums) x = n*x - sum;//归一化//使得avg(nums) = 0//避免浮点精度
        unordered_set<int> h;//存所有状态对应的total
        for(int i = 1 ;i<(1<<m);i++){//折半搜索，先搜索left
            int total = 0;//left某状态的总和
            for(int j = 0;j<m;j++)
                if((i>>j)&1)
                    total += nums[j];//第j位存在
            if(0 == total) return true;//状态总和为0，sumA=sum，可以分割
            h.emplace(total);
        }
        for(int i = 1;i<(1<<(n-m));i++){//再搜索right
            int total = 0;//right某状态的总和
            for(int j = 0;j<n-m;j++)
                if((i>>j)&1)
                    total += nums[m+j];
            if(0 == total) return true;//sumB = sum
            if(i!=(1<<(n-m))-1 && h.count(-total)) return true;
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(n\times 2^{\frac{n}{2}})$， $n$ 是 $nums$ 的长度，一共$O(2\times 2^{\frac{n}{2}})$ 种状态。遍历所有状态的时间复杂度 $O(2^{\frac{n}{2}})$ ，同时遍历每个状态的所有位置的时间复杂度 $O(n)$，二者是乘积关系。
2. 空间复杂度: $O(2^{\frac{n}{2}})$，$h$ 哈希集合的空间复杂度是 $O(2^{\frac{n}{2}})$ 。因为要存储 $left$ 中所有状态的 $total$ 。