力扣每日一题：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

分析：这道题目我们先设几个未知数，a 代表A数组的长度，suma 代表A数组的和，b代表数组B的长度。sumb代表数组B的和，然后我们就可以列出方程

/**
 *          a+b = n ;
 *         suma+sumb =sum ;
 *         suma/a =sumb/b ;
 *         suma = a*sumb/b;
 *         a*sumb/b + sumb =sum ;
 *         n*sumb/b = sum
 *         n*sumb = b*sum ;
 *
 *         sumb = b*sum / n ;
 *         sumb/b = sum / n  ;
 *
 */

可以看到的是 数组B的平均值等于原数组的平均值。如果我们不对原数组进行数据处理的话，我们每次枚举出的组合都要求平均值，我们就可以直接让原数组的每个元素都减去数组的平均值，

题目就转化为：在数组 numsnumsnums 中找出一个子数组 A，使得其和为 0。

数组 nums 的长度范围为 [1,30][1, 30][1,30]，如果我们使用暴力枚举子数组的方法，时间复杂度为 O(2^n))，会超时。我们可以使用折半查找的方法，将时间复杂度降低到 O(2^{n/2})

我们将数组 nums 分成左右两部分，那么子数组 AAA 可能存在三种情况：

子数组 AAA 完全在数组 nums 的左半部分；
子数组 AAA 完全在数组 nums 的右半部分；
子数组 AAA 一部分在数组 nums 的左半部分，一部分在数组 nums 的右半部分。

我们可以使用二进制枚举的方法，先枚举左半部分所有子数组的和，如果存在一个子数组和为 0，直接返回 true，否则我们将其存入哈希表 left 中；然后枚举右半部分所有子数组的和，如果存在一个子数组和为 0，直接返回 true，否则我们判断此时哈希表 vis 中是否存在该和的相反数，如果存在，直接返回 true。

需要注意的是，我们不能同时全选左半部分和右半部分，因为这样会导致子数组 B 为空，这是不符合题意的。在实现上，我们只需要考虑数组的 n−1 个数。

废话不多说直接上代码：

AC代码：

class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        if(nums.length==1){
            return  false ;
        }
 
        int n = nums.length;
        int m = n /2 ;
        int sum = 0 ;
        for (int num : nums) {
            sum += num ;
        }
 
        for (int i =0 ;i
            nums[i] = nums[i] * n - sum ;
        }
 
        Set left = new HashSet<>() ;
 
        for(int i =1 ;i<(1<
            int tot = 0 ;
            for (int j = 0 ;j
                if ((i&(1<0){
                    tot += nums[j] ;
                }
            }
 
            if (tot==0){
                return  true ;
            }
 
            left.add(tot) ;
 
        }
 
        int rsum  = 0 ;
        for(int i = m ;i
            rsum += nums[i] ;
        }
 
        for (int i =1 ;i<(1<<(n-m));i++){
            int tot =0  ;
            for (int j = m ;j
                if ((i& (1<<(j-m)))!=0){
                    tot += nums[j] ;
                }
            }
 
            if (tot ==0|| (rsum!=tot && left.contains(-tot) )){
                return  true ;
            }
 
        }
 
        return  false ;
 
    }
}