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
动态规划
令n=nums.length half=n/2。不失一般性，令A的长度小于等于B，则lena的长度取值范围[1,half]，lenb=n-lena。
数组A的和为：Sumi = 0 : n − 1 \Large_{i=0}^{:n-1}i=0:n−1nums[i]*lena/n ,数组A的和必须是整数。nums[i]的和最大为104*30 ，lean最大为15，可以直接相乘，看对n的余数是否为0。如果超出整数范围，可以先对lena和n约分。
预处理CountToTotal
将nums分成两部分。vLeft[i]记录所有从nums[0,half)选择i个数 可能的和。 vRight[i]记录所有从nums[half,n)中选择i个数的和。下面以vLeft为例，vRightei类似。三层循环
第一层循环：枚举[0,half)。时间复杂度O(n)
第二层循环：从大到小枚举vLeft[j]。 时间复杂度(n)。
第三层循环：枚举vLeft[j-1]。 时间复杂度O(2^n)
动态规划的转移方程：本轮的vLeft[j]一定是上一轮的vLeft[j-1]+nums[i]。总时间复杂度O(1515215) 约106
处理
第一层循环：用变量i枚举lena。
第二层循环：枚举A从左边选择了j个元素，j的取值范围[0,i]。
第三层循环：通过iLeft枚举vLeft[j]，看vRight[i-j]是否存在totalA - iLeft。
时间复杂度: O(nn2n)
代码
核心代码
int GCD(int n1, int n2) { int t1 = min(n1, n2); int t2 = max(n1, n2); if (0 == t1) { return t2; } return GCD(t2 % t1, t1); } class Solution { public: bool splitArraySameAverage(vector<int>& nums) { const int n = nums.size(); const int half = n / 2; vector<unordered_set<int>> vLeft(1), vRight(1); CountToTotal( vLeft, nums.data(),0, half); CountToTotal(vRight, nums.data()+half, 0, n-half); const int total = std::accumulate(nums.begin(), nums.end(),0); for (int i = 1; i <= half; i++) { const int iGCD = GCD(i, n); if (0 != total % (n / iGCD)) { continue;//A的和必定为整数 } const int totalA = total * i / n; for (int j = 0; j <= i; j++) {// A数组总共选择i个，其中从左边选择j个 for (const auto& iLeft : vLeft[j]) { if (vRight[i - j].count(totalA - iLeft)) { return true; } } } } return false; } void CountToTotal(std::vector<std::unordered_set<int>>& v, const int* p,int left,int r) { v[0].emplace(0); for (int i = left; i < r ; i++) { v.emplace_back(); for (int j = v.size() - 1; j >= 1; j--) { for (const auto& pre : v[j - 1]) { v[j].emplace(pre + p[i]); } } } } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; { Solution sln; nums = { 1,2,3,4,5,6,7,8 }; auto res = sln.splitArraySameAverage(nums); Assert(true, res); } { Solution sln; nums = { 3,1}; auto res = sln.splitArraySameAverage(nums); Assert(false, res); } { Solution sln; nums = { 18,10,5,3 }; auto res = sln.splitArraySameAverage(nums); Assert(false, res); } }
2023年1月
class Solution { public: bool splitArraySameAverage(vector& nums) { if (1 == nums.size()) { return false; } const int iLeftMaxLen = nums.size() / 2; const int iRightMaxLen = nums.size() - iLeftMaxLen; vector vLeftLenSums(iLeftMaxLen+1),vRightLenSums(iRightMaxLen+1); vLeftLenSums[0].insert(0); for (int i = 0; i < iLeftMaxLen; i++) { for (int j = i ; j >=0 ; j-- ) { for (auto& it : vLeftLenSums[j]) { vLeftLenSums[j + 1].insert(it +nums[i]); } } vLeftLenSums[1].insert(nums[i]); } vRightLenSums[0].insert(0); for (int i = iLeftMaxLen; i < nums.size(); i++) { for (int j = i - iLeftMaxLen; j >= 0; j–) { for (auto& it : vRightLenSums[j]) { vRightLenSums[j + 1].insert(it + nums[i]); } } } int iTotalSum = std::accumulate(nums.begin(), nums.end(), 0); for (int iALen = 1; iALen + 1 <= nums.size(); iALen++) { double dSum = iTotalSum 1.0 / nums.size() iALen; int iSum = dSum; bool bInt = ((dSum - iSum) < 0.0001) || ((dSum - iSum) > 0.9999); if (!bInt) { continue; } for (int iLeftLen = max(0,iALen-iRightMaxLen); (iLeftLen <= min(iALen, iLeftMaxLen)); iLeftLen++) { for (const auto& it : vLeftLenSums[iLeftLen]) { if (vRightLenSums[iALen - iLeftLen].count(iSum - it)) { return true; } } } } return false; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
