805.数组的均值分割

链接：805.数组的均值分割
难度：Hard
标签：位运算、数组、数学、动态规划、状态压缩
简介：我们要将  nums  数组中的每个元素移动到  A  数组 或者  B  数组中，使得  A  数组和  B  数组不为空，并且  average(A) == average(B) 。

题解 1 - cpp

• 编辑时间：2022-11-14
• 执行用时：148ms
• 内存消耗：18.1MB
• 编程语言：cpp
• 解法介绍：折半搜索，利用二进制统计前半部分取 n 个数的 sum 存入 map，再统计后半部分取 n 个数，两者相加。

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size(), half = n / 2,
            sum = accumulate(nums.begin(), nums.end(), 0);
        unordered_map<int, unordered_set<int>> m;
        for (int i = 0, len = 1 << half; i < len; i++) {
            int total = 0, cnt = 0;
            for (int j = 0; j < half; j++) {
                if ((i & (1 << j)) == 0) continue;
                total += nums[j];
                cnt++;
            }
            m[cnt].insert(total);
        }
        for (int i = 0; i < (1 << (n - half)); i++) {
            int total = 0, cnt = 0;
            for (int j = half; j < n; j++) {
                if ((i & 1 << (j - half)) == 0) continue;
                total += nums[j];
                cnt++;
            }
            // j : 左边拿几个数
            for (int j = max(1, cnt); j < n - 1; j++) {
                if (j * sum % n != 0) continue;
                int prevCnt = j - cnt;
                if (!m.count(prevCnt)) continue;
                int leftTotal = j * sum / n;
                int prevTotal = leftTotal - total;
                if (!m[prevCnt].count(prevTotal)) continue;
                return true;
            }
        }
        return false;
    }
};

题解 2 - cpp

• 编辑时间：2022-11-14
• 执行用时：176ms
• 内存消耗：51.3MB
• 编程语言：cpp
• 解法介绍：同上。

class Solution {
public:
    bool splitArraySameAverage(vector<int>& nums) {
        int n = nums.size(), half = n / 2,
            sum = accumulate(nums.begin(), nums.end(), 0);
        unordered_map<int, unordered_set<int>> m;
        for (int i = 0, len = 1 << half; i < len; i++) {
            int total = 0, cnt = 0;
            for (int j = 0; j < half; j++) {
                if ((i & (1 << j)) == 0) continue;
                total += nums[j];
                cnt++;
            }
            m[total].insert(cnt);
        }
        for (int i = 0; i < (1 << (n - half)); i++) {
            int total = 0, cnt = 0;
            for (int j = half; j < n; j++) {
                if ((i & 1 << (j - half)) == 0) continue;
                total += nums[j];
                cnt++;
            }
            // j : 左边拿几个数
            for (int j = max(1, cnt); j < n - 1; j++) {
                if (j * sum % n != 0) continue;
                int need = j * sum / n - total;
                if (!m.count(need)) continue;
                if (!m[need].count(j - cnt)) continue;
                return true;
            }
        }
        return false;
    }
}