正整数数组拆分等均值子数组：代码判断逻辑问题求助

首先得点出你遇到的核心问题：用两个子数组的平均值直接比较来决定元素移动方向，很容易陷入循环或者导致其中一个数组被清空——比如当其中一个数组只剩单个元素时，它的平均值就是自身，和另一个多元素数组的平均值对比可能出现反向判断，来回移动元素最后把一个数组掏空。

先搞懂问题本质 #

其实，要拆分出两个平均值相同的子数组，这两个子数组的平均值必须等于原数组的平均值。推导一下：
假设原数组总和为S，长度为n；子数组1总和s1、长度k，子数组2总和s2、长度n-k。
如果s1/k = s2/(n-k)，交叉相乘后可得s1*n = k*S，也就是s1/k = S/n——即子数组的平均值等于原数组的平均值。

这个结论能帮你跳出“对比两个子数组平均值”的误区，转而基于原数组的平均值来做决策。

你的代码问题修正方案 #

1. 先跳过无效情况：先计算原数组的总和S和长度n，如果不存在k（1≤k<n）使得S*k能被n整除，那直接返回“无法拆分”，因为这样的子数组不存在。
2. 用原数组平均值做判断基准：
   • 计算原数组的平均值avg = (double)S / n（或者用分数形式S/n避免浮点精度问题，比如用总和和长度的比例比较）。
   • 把元素分成三组：大于avg的、小于avg的、等于avg的。等于avg的元素可以随意分配到两个数组，不影响平均值。
   • 对于大于和小于avg的元素，我们需要调整它们的分配：比如从大于avg的数组中取出元素放到小于的数组，或者反过来，直到两边的子数组总和除以长度等于avg。
   • 绝对不要在其中一个数组为空的时候做平均值对比，这时候的平均值没有意义，会导致错误决策。

示例修正后的逻辑片段 #

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArraySplit {
    public static void main(String[] args) {
        int[] arr = {1,2,4,5};
        int totalSum = Arrays.stream(arr).sum();
        int n = arr.length;
        double avg = (double) totalSum / n;

        // 分组
        List<Integer> greater = new ArrayList<>();
        List<Integer> lesser = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();

        for (int num : arr) {
            if (num > avg) {
                greater.add(num);
            } else if (num < avg) {
                lesser.add(num);
            } else {
                equal.add(num);
            }
        }

        // 计算偏差：greater组每个元素与avg的差值之和
        double greaterDeviation = greater.stream().mapToDouble(num -> num - avg).sum();

        // 贪心调整分组，直到偏差趋近于0（处理浮点误差）
        while (greaterDeviation > 1e-9) {
            int num = greater.remove(greater.size()-1);
            lesser.add(num);
            greaterDeviation -= 2*(num - avg);
        }

        // 分配等于avg的元素
        greater.addAll(equal.subList(0, equal.size()/2));
        lesser.addAll(equal.subList(equal.size()/2, equal.size()));

        // 输出结果
        System.out.println(greater); // [1,5]
        System.out.println(lesser); // [2,4]
    }
}

为什么原来的判断会导致数组清空？ #

举个极端例子：假设数组是[1,3]，原数组平均值是2。如果一开始把1放到数组1，3放到数组2，数组1平均值1 < 数组2平均值3，你可能会把3移到数组1，此时数组1是[1,3]，数组2为空——这时候数组2的平均值不存在，你的判断逻辑就会出错，甚至继续把元素移到空数组，导致彻底清空。

而用原数组平均值做基准，你会直接知道1<2，3>2，只需要调整这两个元素的分配（其实它们本身就是符合条件的子数组），不会出现空数组的情况。

内容的提问来源于stack exchange，提问作者SiddP