LeetCode 805. 数组的均值分割
题目描述
题意分析
将数组中的每个元素分到两组之一，要求两组都非空，且两组元素的平均值相同，判断是否存在这样的分配。不要求连续，也不要求两组元素个数相同；相同数值的不同位置仍是可以分别选择的元素。
判断的是平均值相等，不是两组总和相等。数组只有一个元素时无法形成两个非空组；零是合法元素。题目最多有三十个元素，可以按数量记录子集和，也可以通过折半枚举降低对数值范围的依赖。
解法：子集和 DP
核心思路
[!blue]
设总元素数为
n，总和为S。选择一组包含k个元素、和为a，另一组就包含n - k个元素、和为S - a。平均值相等要求a / k = (S - a) / (n - k)，交叉相乘并整理得到a * n = S * k。因此只需找到一个非空且不含全部元素的子集，使和等于整数目标S * k / n。对不同的选择数量，目标和不同，不能只用一张不区分数量的可达和表。定义
dp[k]为已经处理过的元素中，恰好选择k个时能够得到的所有和。初始dp[0]只包含零，表示空选择；其他集合为空。遇到当前元素
num时，可以不选它，保留原集合中的和；也可以把它接到任意一个旧的k - 1元素方案上，将s + num加入dp[k]。集合会自动合并不同选择路径产生的相同和，因为本题只判断是否存在，不需要统计方案数量。选择数量必须从大到小更新。这样读取
dp[k - 1]时，它还没有被本轮的num扩展，同一个数组位置就不会在一个方案里重复使用。若从小到大，刚加入num的和可能立刻被下一数量读取，错误地再次选择同一元素。全部元素处理完后，枚举
k = 1到n - 1。先检查S * k能否被n整除，不整除说明整数子集不可能达到这个平均值；能够整除时，再检查目标和是否属于dp[k]。排除零个和全部元素，就同时保证两组都非空。
解题步骤
- 计算
n、总和S，为各个选择数量准备可达和集合，只将零加入dp[0]。- 遍历每个元素，按数量从
n - 1倒序到1更新。- 对旧
dp[k - 1]中的每个和s，把s + num加入dp[k]，原有状态保留。- 枚举合法组大小
1到n - 1，只有S * k % n == 0时才计算对应目标和。- 任意一个目标和可达即返回
true，否则返回false。
代码实现
class Solution {
public boolean splitArraySameAverage(int[] nums) {
int n = nums.length;
int sum = 0;
for (int v : nums) {
sum += v;
}
List<Set<Integer>> dp = new ArrayList<>();
for (int i = 0; i <= n; i++) {
dp.add(new HashSet<>());
}
dp.get(0).add(0);
for (int num : nums) {
// 数量倒序，读取的上一数量仍未使用当前元素
for (int k = n - 1; k >= 1; k--) {
for (int s : dp.get(k - 1)) {
dp.get(k).add(s + num);
}
}
}
for (int k = 1; k < n; k++) {
// 目标和必须为整数，先检查整除再计算目标
if (sum * k % n != 0) {
continue;
}
int target = sum * k / n;
if (dp.get(k).contains(target)) {
return true;
}
}
return false;
}
}
func splitArraySameAverage(nums []int) bool {
n := len(nums)
sum := 0
for _, v := range nums {
sum += v
}
dp := make([]map[int]struct{}, n+1)
dp[0] = make(map[int]struct{})
dp[0][0] = struct{}{}
for _, num := range nums {
// 数量倒序，读取的上一数量仍未使用当前元素
for k := n - 1; k >= 1; k-- {
if dp[k] == nil {
dp[k] = make(map[int]struct{})
}
for s := range dp[k-1] {
dp[k][s+num] = struct{}{}
}
}
}
for k := 1; k < n; k++ {
// 目标和必须为整数，先检查整除再计算目标
if sum*k%n != 0 {
continue
}
target := sum * k / n
if _, ok := dp[k][target]; ok {
return true
}
}
return false
}
复杂度分析
- 时间复杂度：期望 $O(n^2Q)$，
Q为各个可达和集合的最大大小，每个元素依次扩展各个数量的集合。由于元素非负，Q不超过S + 1，这是复杂度依赖总和值大小的伪多项式方法。- 空间复杂度：$O(nQ)$，按所选元素个数分别保存可达和集合。
关键点总结
[!green]
- 交叉相乘把平均值相等改成整数关系，避免浮点比较。
- 子集和必须和选择数量配套记录，才能确定应查询的目标。
- 倒序更新数量，保证每个数组位置在一个方案中只使用一次。
- 只检查非空真子集，另一组作为补集也自然非空。
解法：折半枚举零和子集
核心思路
[!blue]
沿用
a * n = S * k，把每个元素变换成value = nums[i] * n - S。选择k个变换值后的总和就是a * n - S * k，所以原问题等价于：是否存在一个非空、且不是全集的零和子集。这个变换只使用整数，并且不要求选择位置连续。最多三十个元素，直接枚举全部子集规模较大；将它们分成左右两半，每半最多十五个元素，各自枚举非空子集即可。子集完全位于某一半且和为零时，可以直接成功，因为另一半仍有元素，所选不可能是全集。
对需要跨越两半的方案，枚举左半子集时，用哈希表保存“子集和到该和所需的最少元素数”。右半某个子集和为
s时，只需查询左半是否存在和为-s的子集，两部分相加就为零。左右元素来源不重叠，因此不需要担心重复使用同一个位置。全部变换值的和始终为零，所以必须排除把左右两半全选的情况。两边枚举都只含非空子集，再检查总选择数量严格小于
n，就保证得到非空真子集。同一个左半和只保存最少元素数已经足够：它为右半留下最多未选空间；如果最少数量也会凑成全集，其他更大的数量更不可能合法。每个非空真子集要么只在某一半，要么拆成两个非空部分，上述两类检查覆盖了所有可能。枚举规模只依赖元素个数，与原始总和大小无关；按本题数值上限，变换值及其子集和都能使用整数保存。
解题步骤
- 少于两个元素时返回
false，否则计算总和并生成变换值数组。- 从中间分成左右两半，用位掩码枚举左半所有非空子集，计算其和与数量。
- 左半和为零时直接成功；否则在哈希表中保留该和对应的最少元素数。
- 同样枚举右半非空子集；本身和为零时成功，否则查找左半的相反和。
- 找到匹配且两部分数量之和小于
n时返回true；全部枚举结束仍未命中则返回false。
代码实现
class Solution {
public boolean splitArraySameAverage(int[] nums) {
int n = nums.length;
if (n < 2) {
return false;
}
int total = 0;
for (int num : nums) {
total += num;
}
int[] adjusted = new int[n];
for (int i = 0; i < n; i++) {
adjusted[i] = nums[i] * n - total;
}
int middle = n / 2;
Map<Integer, Integer> leftMinCount = new HashMap<>();
for (int mask = 1; mask < (1 << middle); mask++) {
int sum = 0;
int count = 0;
for (int i = 0; i < middle; i++) {
if ((mask & (1 << i)) != 0) {
sum += adjusted[i];
count++;
}
}
if (sum == 0) {
return true;
}
Integer previous = leftMinCount.get(sum);
if (previous == null || count < previous) {
leftMinCount.put(sum, count);
}
}
int rightSize = n - middle;
for (int mask = 1; mask < (1 << rightSize); mask++) {
int sum = 0;
int count = 0;
for (int i = 0; i < rightSize; i++) {
if ((mask & (1 << i)) != 0) {
sum += adjusted[middle + i];
count++;
}
}
if (sum == 0) {
return true;
}
Integer leftCount = leftMinCount.get(-sum);
if (leftCount != null && leftCount + count < n) {
return true;
}
}
return false;
}
}
func splitArraySameAverage(nums []int) bool {
n := len(nums)
if n < 2 {
return false
}
total := 0
for _, num := range nums {
total += num
}
adjusted := make([]int, n)
for i, num := range nums {
adjusted[i] = num*n - total
}
middle := n / 2
leftMinCount := make(map[int]int)
for mask := 1; mask < 1<<middle; mask++ {
sum := 0
count := 0
for i := 0; i < middle; i++ {
if mask&(1<<i) != 0 {
sum += adjusted[i]
count++
}
}
if sum == 0 {
return true
}
if previous, exists := leftMinCount[sum]; !exists || count < previous {
leftMinCount[sum] = count
}
}
rightSize := n - middle
for mask := 1; mask < 1<<rightSize; mask++ {
sum := 0
count := 0
for i := 0; i < rightSize; i++ {
if mask&(1<<i) != 0 {
sum += adjusted[middle+i]
count++
}
}
if sum == 0 {
return true
}
if leftCount, exists := leftMinCount[-sum]; exists && leftCount+count < n {
return true
}
}
return false
}
复杂度分析
- 时间复杂度：期望 $O(n \cdot 2^{\lceil n/2\rceil})$，每半枚举全部子集，每个子集逐位累加至多半个数组，哈希查询按期望常数时间计算。
- 空间复杂度：$O(n + 2^{\lfloor n/2\rfloor})$，保存变换数组和左半不同子集和对应的最少数量，右半边枚举边查询。
关键点总结
[!green]
- 将平均值条件变成整数零和条件，随后只需组合两个半边的子集和。
- 单半边非空零和子集可直接成功，跨半边时检查相反和与总数量。
- 排除全集是必要约束，因为全部变换值相加总是零。
- 同和保留最少元素数，足以判断是否还能给补集留下至少一个元素。
易错点总结
[!yellow]
- 直接寻找总和的一半，额外要求了两组数量相等，不能覆盖原题的全部合法分割。
- 目标计算前不检查整除，会使用向下取整的和，接受平均值并不相等的方案。
- 子集 DP 正序更新数量，可能在同一轮重复使用当前元素。
- 只记可达和而不记数量，无法区分同一个和对应的不同平均值。
- 折半枚举只发现零和就不检查选取数量，空集或全集都会因为变换而错误命中。
- 折半合并时覆盖掉同和的较少元素记录，可能只留下会凑成全集的选择，漏掉合法真子集。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 416. 分割等和子集 | 中等 | 同样转成子集选择，但平均值相等还依赖被选元素数量，不能只找总和一半。 |
| 2035. 将数组分成两个数组并最小化数组和的差 | 困难 | 同样可以按选取数量组织折半枚举的子集和，本题判断平均值条件，原题最小化两组和差。 |