题目大意：
给定的整数数组 A ，我们要将 A数组 中的每个元素移动到 B数组 或者 C数组中。（B数组和C数组在开始的时候都为空）
返回true ，当且仅当在我们的完成这样的移动后，可使得B数组的平均值和C数组的平均值相等，并且B数组和C数组都不为空。
示例: 输入: [1,2,3,4,5,6,7,8] 输出: true 解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
注意:
A数组的长度范围为[1, 30].A[i]的数据范围为[0, 10000].
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=805
思路分析：
说实话，刚读完这题后有点蒙，不知道该从何下手，后来仔细琢磨半天后，终于把思路理顺了。其实从开始刷LeetCode开始，每次做完题之后都会发现，不论题目多么的变态，最终都有办法将复杂问题简单化。本题也不例外，我们可以试着用下面的逻辑来分析一下。
第一，题目要求将一个数组分成两个子数组，且这两子数组的平均值相同。也就是说，两个子数组的平均值应该都等于整个数组的平均值。
第二，那么如何判断该数组中是否存在这样的分割呢？我们可以将数组分成两部分，一部分大于平均数，另一部分小于平均数。接下来，我们需要做去平均数操作。也就是说，把数组中所有的元素，都分别减去平均数，这样，左边数组都会变为负数，右边数组都会变为整数，同时整个数组的平均数应该是0。当然，如果原数组中存在等于平均数的元素（或者去平均后存在等于0的元素），这时可以直接返回True！如果不存在的话，那么我们需要看能不能在左边的子数组中找出一些元素再加上右边子数组的一些元素，所有元素相加如果等于0，则返回True，反之，False。
第三，当然想到第二步基本已经可以了。如果还想将问题再简化一点的话，我们可以将左边子数组内的所有负数元素取绝对值，都变成正数，这样，问题就变为，在左边子数组中找到一组数字（必须为左子数组的真子集）的和等于右边子数组中一组数字的和。
分析到这里，我们只需要分别将左右两个子数组的所有求和结果便利出来，然后比较是否有相同的和即可！
那么，如何把一个数组中所有可能的组合的和遍历出来呢？其实这跟求一个数组的所有子数组的思路是一致的，代码不难，如下：
// 数组中所有可能的组合的和的结果集（好绕口）
Set<Integer> mSumSet = new HashSet<>();
// 循环原数组
for (int m : listM) {
// 为了不影响结果集的循环，定义一个临时结果集
Set<Integer> mSumSetTemp = new HashSet<>();
// 循环结果集
for (int mm : mSumSet) {
// 将结果集中的每个元素加上当前元素作为新元素存入临时结果集
mSumSetTemp.add(m + mm);
}
// 循环后将临时结果集全部加到结果集中
mSumSet.addAll(mSumSetTemp);
// 将当前元素加入结果集。继续循环下一个元素直到所有元素循环完毕
mSumSet.add(m);
}到此为止，核心思路都分析完了，看下完整代码吧。
public boolean splitArraySameAverage(int[] A) {
// 数组长度
int aLength = A.length;
// 如果数组少于2个元素，还分个毛线。
if (aLength < 2) {
return false;
}
// 如果数组只有两个元素，只需要判断这哥俩是否相同即可。
if (aLength == 2) {
return A[0] == A[1];
}
// 数组所有元素之和
int sum = 0;
for (int i = 0; i < aLength; i++) {
A[i] = A[i] * aLength;
sum += A[i];
}
// 数组的平均数
int average = sum / aLength;
// 定义一个负数List（所有小于平均数的元素）
List<Integer> listM = new ArrayList<>();
// 定义一个正数List（所有大于平均数的元素）
List<Integer> listP = new ArrayList<>();
// 负数List中所有元素之和。（后面要用到）
int mSum = 0;
// 循环数组，将每个元素去平均数，并将元素分别存入负数List和正数List
for (int i = 0; i < aLength; i++) {
int a = A[i];
int newA = a - average;
// 元素去平均后为0的话，直接返回True。
if (newA == 0) {
return true;
}
// 元素大于0，存入正数List
if (newA > 0) {
// 如果负数List存在相同的元素，返回True
if (listM.contains(newA)) {
return true;
}
listP.add(newA);
}
// 元素小于0，取绝对值后存入负数List
else {
// 如果正数List存在相同的元素，返回True
if (listP.contains(Math.abs(newA))) {
return true;
}
// 负数List中所有元素之和。（后面要用到）
mSum += Math.abs(newA);
listM.add(Math.abs(newA));
}
}
// 遍历出负数数组中所有可能的组合的和
Set<Integer> mSumSet = new HashSet<>();
for (int m : listM) {
Set<Integer> mSumSetTemp = new HashSet<>();
for (int mm : mSumSet) {
mSumSetTemp.add(m + mm);
}
mSumSet.addAll(mSumSetTemp);
mSumSet.add(m);
}
// 因为要取真子集，所以要去除掉负数数组所有元素的总和
mSumSet.remove(Integer.valueOf(mSum));
// 遍历出正数数组中所有可能的组合的和
Set<Integer> pSumSet = new HashSet<>();
for (int p : listP) {
Set<Integer> pSumSetTemp = new HashSet<>();
for (int pp : pSumSet) {
// 如果负数数组中存在该值，返回True
if (mSumSet.contains(p + pp)) {
return true;
}
pSumSetTemp.add(p + pp);
}
pSumSet.addAll(pSumSetTemp);
// 如果负数数组中存在该值，返回True
if (mSumSet.contains(p)) {
return true;
}
pSumSet.add(p);
}
return false;
}这种解法的运行时间大概是21ms左右，需要注意的是，这道题中存放所有组合的和的集合用的是HashSet而不是ArrayList，因为HashSet可以自动去除重复，因为是求和操作，所以重复的值是不需要存入结果集的，例如，数组中存在{1,1,2,6,7,8,9,10….}，这里前两个元素都是1，我们只遍历其中一个1的所有组合就可以了，因为第二个1再遍历一次的结果和第一个1是一样的。另外，前两个1相加等于2，数组中第三个元素也是2，所以同理，也只遍历其中一个就好了。使用HashSet的另一个原因是执行速度，因为我们不需要排序，使用它要比有序的ArrayList快很多。
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-805-split-array-with-same-average-java解题思路/