【leetcode】【2022/11/14】805. 数组的均值分割

问题描述：

• 给定你一个整数数组 nums，我们要将 nums 数组中的每个元素移动到 A 数组或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B)。
  • 如果可以完成则返回 true，否则返回 false。
  • 满足 1 <= nums.length <= 30。

核心思路：

• 该题较难，考察了数学推导 + 位运算 + 折半搜索。
• 数学推导部分如下：
  • 首先经过推导可得知，数组 A 或数组 B 的平均值和原数组 nums 的平均值是相等的。
  • 因此将数组中所有数值减去 sum(nums)/n，原问题就可以转换为找到一个数组 A 其求和为 0。【其中 n 为数组长度】
  • 而直接求 nums 的平均值可能会得到浮点值影响最后结果的精度，所以在求平均值前先将 nums 中所有数值乘以数组的长度，再将所有数值减去 sum(nums)，仍然可以将问题转化为找到一个数组 A 其求和为 0。
  • 也就是说，对每一个数值 num 进行 num * n - sum(nums) 的预处理，最后找到 nums 中哪些数求和为 0 即可。
• 而想要计算出所有的子集求和情况，就需要用位运算来维护元素的存取情况：
  • 因为 1 <= n <= 30，所以所有子集的存取有 $2^n$ 种情况，用第 i 位用来判断数组第 i 个元素是否存入数组 A。
  • 因此我们遍历 [1, 1 << n) 即遍历所有存取情况；在每一个子集中遍历数组元素，来获得当前子集求和情况。
  • 但如此计算就是暴力求解，时间复杂度为 $\mathcal{O}(2^n\times n)$，当 n = 30 时自然会超时。
• 解决的办法就是折半搜索：【该思想是本题解的主要难点】
  • 顾名思义就是搜索前半段和后半段，时间复杂度就会缩减为 $\mathcal{O}(2^{\frac{n}{2}}\times n)$。
  • 但此时需要进行讨论，最后子集 A 可能出现三种情况：
    1. 子集元素全部存在于数组前半段；【此时搜索前半段就可以得到某个子集求和为 0】
    2. 子集元素全部存在于数组后半段；【此时搜索后半段就可以得到某个子集求和为 0】
    3. 子集元素存在于前半段和后半段。
  • 情况 3 较为复杂，此时就需要用空间换时间，利用哈希表来保存前半段的所有子集和，在后半段的遍历中利用哈希表中的值即可。
  • 用哈希表来保存值时，还可能出现前半段和后半段元素同时全选的情况，此时需要避免判断该情况，具体看代码注释即可。
• 该题的动态规划是根据 sum(nums) 的范围推导的，也就是根据值域大小来获得所有子集求和的情况，官方题解给出的动态规划解法时间复杂度为 $\mathcal{O}(n^2\times sum(nums))$，一旦求和的范围过大，动态规划解法就可能会超时。

代码实现：

• 折半搜索解法代码实现如下：

  class Solution {
  public:
      bool splitArraySameAverage(vector<int>& nums) {
          int n = nums.size(); // n 的取值范围为 [1, 30]
          if(n == 1) return false;
          int sum = accumulate(nums.begin(), nums.end(), 0);
          for(int& num : nums) num = num * n - sum; // 原本是 num = num - sum/n，但这样写会有精度问题
          int m = n >> 1; // 折半计算
          unordered_set<int> ss;
          for(int i = 1; i < (1 << m); ++i) { // 二进制表示选择结果
              int t = 0;
              for(int j = 0; j < m; ++j)
                  if(i & (1 << j)) t += nums[j]; // 求和子数组
              if(t == 0) return true;
              ss.insert(t);
          }
          for(int i = 1; i < 1 << (n-m); ++i) {
              int t = 0;
              for (int j = 0; j < (n-m); ++j)
                  if(i & (1 << j)) t += nums[m+j];
              if(t == 0 or (i != (1 << (n-m))-1 and ss.count(-t))) return true;
              // 注意 i != (1 << (n-m))-1 表示不能“同时”左子数组全选和右子数组全选，因为同时全选就是整个数组全部选择，则必定返回 true
              // 左子数组全选的情况已经存在 ss 中，所以遍历右子数组之后，判断完右子数组全选不为 0 之后，就需要避免左右子数组同时全选的情况
          }
          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

参考内容：

• 折半查找 + 二进制枚举（详解）