805.split-array-with-same-average.md

题目地址(805. 数组的均值分割)

https://leetcode-cn.com/problems/split-array-with-same-average/

题目描述

给定的整数数组 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]. 

前置知识

• 回溯

公司

• 暂无

思路

实际上分出的两个列表 B 和 C 的均值都等于列表 A 的均值，这是本题的入手点。以下是证明：

令 B 的长度为 K，A 的长度为 N。 则有 sum(B)/K = sum(C)/(N-K)。

进而：

sum(B) * (N - K) = sum(C) * K sum(B) * N = (sum(B) + sum(C)) * K sum(B) / K = (sum(B) + sum(C)) / N sum(B) / K = sum(A) / N 

因此我们可以枚举所有的 A 的大小 i，相应地 B 的大小就是 n - i，其中 n 为数组 A 的大小。

而由于两个列表 B 和 C 的均值都等于列表 A 的均值。因此可以提前计算出 A 的均值 avg，那么 A 的总和其实就是 i * avg ，我们使用回溯找到一个和为 i * avg 的组合，即可返回 true，否则返回 false。

值得注意的是，我们只需要枚举 i 为 1 到 N//2 范围即可，这可以达到剪枝的效果。

核心代码：

defsplitArraySameAverage(self, A: List[int]) ->bool: n=len(A) avg=sum(A) /nforiinrange(1, n//2+1): forcombinationincombinations(A, i): ifabs(sum(combination) -avg*i) <1e-6: returnTruereturnFalse

上面代码由于回溯里面嵌套了 sum，因此时间复杂度为回溯的时间复杂度 * sum 的时间复杂度，因此总的时间复杂度在最坏的情况下是 $n * 2^n$。代入题目的 n 范围是 30，一般这种复杂度只能解决 20 以下的题目，因此需要考虑优化。

我们可以不计算出来所有的组合之后再求和，而是直接计算所有的和的组合，这种算法的时间复杂度为 $2^n$。

核心代码：

defsplitArraySameAverage(self, A: List[int]) ->bool: n=len(A) avg=sum(A) /nforiinrange(1, n//2+1): forsincombinationSum(A, i): ifabs(s-avg*i) <1e-6: returnTruereturnFalse

但是遗憾的是，这仍然不足以通过所有的测试用例。

接下来，我们可以通过进一步剪枝的手段来达到 AC 的目的。 很多回溯的题目都是基于剪枝来完成的。剪枝是回溯问题的核心考点。

这个技巧就是双向搜索，双向搜索相比之前的回溯可达到减少指数数字的效果，从 $O(2^n)$ 降低到 $O(2^(N//2))$。代入题目，这样指数变为了 30/2 = 15，就可以通过了。

具体地，我们可以 combinationSum A 数组的一半（不妨称 A1），然后 combinationSum A 数组的令一半（不妨称 A2），那么 A1 和 A2 的总和如果是 avg * i 不也行么？简单起见，我们可以令 A1 为数组 A 的前一半， A2 为数组的后一半。

同时，为了避免这种加法，我们可以对问题进行一个转化。即将数组 A 的所有数都减去 avg，这样问题转化为找到一个和为 0 的组合，即可以找到一个和为 avg * i 的组合。

关键点

• 双端搜索

代码

• 语言支持：Python3

Python3 Code:

classSolution(object): defsplitArraySameAverage(self, A): fromfractionsimportFractionN=len(A) total=sum(A) A= [a-Fraction(total, N) forainA] # 转化后的 A，免于计算 sumifN==1: returnFalseS1=set() # 所有 B 可能的和的集合foriinrange(N//2): # {a + A[i] for a in S1} 在之前选择的基础上选择 A[i] 的新集合# {A[i]} 是仅选择 A[i] 的新集合# S1 是不选择 A[i] 的集合# | 是集合并操作S1= {a+A[i] forainS1} |S1| {A[i]} if0inS1: returnTrueS2=set() # 所有 C 可能的和的集合foriinrange(N//2, N): S2= {a+A[i] forainS2} |S2| {A[i]} if0inS2: returnTrue# 如果 S1 和 S2 都没有和为 0 的组合。那么我们就需要从 S1 和 S2 分别找一个 a 和 b，看其和是否能达到 0. 如果可以，说明也能满足题意# 为了避免 B 或者 C 为空，我们增加一个这样的判断： (ha, -ha) != (sleft, sright)sleft=sum(A[i] foriinrange(N//2)) sright=sum(A[i] foriinrange(N//2, N)) returnany(-hainS2and (ha, -ha) != (sleft, sright) forhainS1)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(2^(N//2))$
• 空间复杂度：$O(2^(N//2))$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。