LeetCode 805. 数组的均值分割

将数组nums分成两个平均值相等的子数组A和B，由于两个数组平均值相等，不难又等式推导出他们的平均值等于数组nums的平均值。

由于平均值可能为小数，在计算时可能会因为精度的差异对结果造成影响，在这里使用nums'[i] = nums[i] * n - sum，将数组的平均值化为0，并且保持每个数组的平均值也为0，sum(nums'[i]) = sum(nums[i]) * n - sum * n = 0

接下来问题就转化成了在数组nums'中寻找一个和为0的子数组A（两个子数组的和都为0，且数组总和为0，因此只需要找出一个和为0的数组即可），且子数组不为数组nums'

对于这种问题有很多种解法，常见的有DFS和二进制枚举法，但是本质上都是枚举，在本题中直接使用DFS和二进制枚举都会导致超时。

DFS需要更加繁琐的剪枝（主要是没想过）

在这里对二进制枚举进行优化，将数组分为左右两段，那么子数组存在三种可能。

1. 子数组在左段
2. 子数组在右段
3. 子数组分布在左右两段（变为，在左右两段中寻找sum_l = - sum_r）

要注意这里找出的子数组不能等于数组

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);
        // 消除小数的干扰
        for(int i = 0; i < n; i++)
            nums[i] = nums[i] * n - sum;
        // 处理左段
        unordered_set<int> dir;
        int m = n >> 1;
        for(int i = 1; i < 1 << m; i++)
        {
            sum = 0;
            for(int j = 0; j < m; j++)
            {
                if(i >> j & 1)
                    sum += nums[j];
            }
            if(sum == 0)
                return true;
            dir.insert(sum);
        }
        // 子数组不在左段中，继续处理右段
        for(int i = 1; i < 1 << (n - m); i++)
        {
            sum = 0;
            for(int j = m; j < n; j++)
            {
                if(i >> (j - m) & 1)
                    sum += nums[j];
            }
            // i != (1 << (n - m)) - 1 保证找到的子数组不为整个数组
            if(sum == 0 || (dir.count(-sum) && i != (1 << (n - m)) - 1))
                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
29
30
31
32
33
34
35
36
37
38
39
40
41