难度: Hard
给定你一个整数数组 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 <= 300 <= nums[i] <= 104运行时间: 157 ms
内存: 39.8 MB
class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
m = n // 2
s = sum(nums)
if all(s * i % n for i in range(1, m + 1)):
return False
dp = [set() for _ in range(m + 1)]
dp[0].add(0)
for num in nums:
for i in range(m, 0, -1):
for x in dp[i - 1]:
curr = x + num
if curr * n == s * i:
return True
dp[i].add(curr)
return False
这个题解使用动态规划的思路来判断是否可以将数组分割成两个平均值相等的子数组。首先判断数组总和 s 是否存在可以被 n 整除的子数组长度 i，如果不存在则直接返回 False。然后使用一个长度为 m+1 的 dp 数组，其中 m 为数组长度的一半，dp[i] 表示长度为 i 的子数组的所有可能的元素和集合。遍历数组 nums 中的每个元素，对于每个 dp[i-1] 中的元素和 x，判断 x+num 是否等于 s*i/n，即是否存在一个长度为 i 平均值等于 s/n 的子数组，如果存在则返回 True。最后如果找不到则返回 False。
时间复杂度: O(n * m * sum(nums))
空间复杂度: O(m * sum(nums))
class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
n = len(nums)
m = n // 2
s = sum(nums)
# 判断是否存在长度为 i 的子数组平均值等于 s/n
if all(s * i % n for i in range(1, m + 1)):
return False
dp = [set() for _ in range(m + 1)] # dp[i] 表示长度为 i 的子数组的所有可能的元素和集合
dp[0].add(0)
for num in nums: # 遍历数组 nums 中的每个元素
for i in range(m, 0, -1): # 遍历 m 到 1
for x in dp[i - 1]: # 遍历 dp[i-1] 中的每个元素和
curr = x + num
if curr * n == s * i: # 判断是否存在长度为 i 平均值等于 s/n 的子数组
return True
dp[i].add(curr)
return False
这个检查是为了确认是否存在某个子数组长度i，使得该子数组的平均值可能等于整个数组的平均值。算法首先计算整个数组的平均值s/n，而一个子数组的平均值为其元素和除以其长度。如果存在一个长度为i的子数组其平均值也为s/n，那么其元素和必须是s*i/n。但是s*i/n必须是一个整数，因此我们需要检查s*i是否能整除n。如果对所有1到m+1的i都不能整除，说明不可能分割出任何符合条件的子数组，因此直接返回False。
在动态规划中更新dp数组时，从m遍历到1可以避免元素重复使用的问题。如果从1到m更新，新增加的元素可能会在同一轮中被重复用于更新多个dp[i]，这会导致计算错误。而从m到1更新，保证每个元素在每一轮中只加入一次，确保了元素组合的唯一性和正确性。
当处理大数时，确实可能会面临性能和存储的问题。一种优化方法是使用模运算来减少数字的大小，即在每次加入新的元素和到dp[i]后，可以对某个大的质数取模，从而减小数字的规模。这种方法可能会引入冲突，但在实际应用中可以适当选择模数来平衡正确性和效率。此外，也可以考虑使用更高效的数据结构或算法来优化处理过程，例如利用空间换时间的策略，或者更精细的状态定义来减小状态空间。
这个条件成立表明找到了一个子数组，其元素和为curr，长度为i，并且满足其平均值等于整个数组的平均值s/n。因为curr * n == s * i等价于curr/n = s/i。由于数组可以被分割成多个子数组，其中一个子数组平均值已经证实等于整个数组的平均值，因此剩余部分的平均值也必然等于整个数组的平均值。这样就找到了两个子数组，它们的平均值相等，满足题目条件。