题目简介：
给定你一个整数数组 nums
我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B)。
如果可以完成则返回true ， 否则返回 false 。
注意：对于数组 arr , average(arr) 是 arr 的所有元素除以 arr 长度的和。
示例 1:
1
2
3
| 输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
|
提示:
1 <= nums.length <= 300 <= nums[i] <= 10^4
思路：
由题意得$\frac{sum(A)}{k} = \frac{sum(B)}{n - k}$
化简可得$sum(A) n = (sum(A) + sum(B)) k$
即$ \frac{sum(A)}{k} = \frac{sum(nums)}{n}$
为了方便，我们将nums中的元素都* n - sum(nums)，那么最后问题转化为找到一个子数组A，其元素和为0。
我们将数组一分为二，前一半在搜索过程中将元素和以及对应的元素个数保存下来；
后一半在搜索过程中，观察是否能与前一半的元素和组成为0即可。
tip:
代码如下：
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
public:
bool res = false;
unordered_map<int, int> map;
void solve(vector<int>& nums, int pos, int end, int sum_now, int now_count){
if(sum_now == 0 && now_count < nums.size() && now_count > 0){
res = true;
return;
}
if(pos <= nums.size() / 2){
map[sum_now] = now_count;
}
else{
if(map[-sum_now] != 0 && now_count + map[-sum_now] < nums.size()){
res = true;
return;
}
}
if(pos + 1 <= end){
solve(nums, pos + 1, end, sum_now + nums[pos], now_count + 1);
solve(nums, pos + 1, end, sum_now, now_count);
}
}
bool splitArraySameAverage(vector<int>& nums) {
if(nums.size() == 1)
return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
for(auto& num : nums){
num = num * nums.size() - sum;
}
solve(nums, 0, nums.size() / 2, 0, 0);
solve(nums, nums.size() / 2, nums.size(), 0, 0);
return res;
}
};
|
