LeetCode每日一题——805. 数组的均值分割

简介: 给定你一个整数数组 nums我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中,使得 A 数组和 B 数组不为空,并且 average(A) == average(B) 。

题目

给定你一个整数数组 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

思路

折半搜索:

这里仅给出大致思路,详细折半查找的学习见官方题解官方题解

1.先遍历 A 的前半部分 B=A[:n//2],得到所有子集和的集合 S

2.如果 S 中没有 0,再遍历 A 的后半部分 C=A[n//2:],得到所有子集和的集合 S2

3.如果 S2 中也没有 0,那遍历 S2 中 的 x,判断 -x 是否在 S 中即可。

注意不能选取整个 A,所以不考虑 x=sum© 的情况。证明:

  • C 的子集和都不为 0,那么 C 的任意真子集的和不等于 sum©
  • 因此 x=sum© 必然对应整个 C
  • B 的子集和都不为 0,那么 B 的任意真子集的和不等于 sum(B)
  • 因此 -x=sum(B) 必然对应整个 B

题解

def splitArraySameAverage(self, nums: List[int]) -> bool:
    n, s = len(nums), sum(nums)
    mul = n//gcd(n, s)
    A = [num*mul-mul*s//n for num in nums]
    S = set()
    for x in A[:n//2]:
        S |= {sub+x for sub in S|{0}}
        if 0 in S:
            return True
    S2, rs = set(), sum(A[n//2:])
    for x in A[n//2:]:
        for sub in S2|{0}:
            y = sub+x
            if y != rs and (y==0 or -y in S):
                return True
            S2.add(y)
    return False
目录
相关文章
|
3月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
136 1
|
11月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
109 0
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
11月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
82 4
|
11月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
94 0
Leetcode第三十三题(搜索旋转排序数组)
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
11月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
181 0
|
11月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
76 0
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组