我是看了官方题解一，在看题解评论区，在咨询评论区的大佬，然后来这了，无奈了。。。
上题解一官方代码（忽略我的代码注释）题目：805. 数组的均值分割 题解： 折半搜索
Go
// splitArraySameAverage 数组的均值分割
func splitArraySameAverage(nums []int) bool {
n := len(nums)
if n == 1 {
return false
}
sum := 0
for _, x := range nums {
sum += x
}
for i := range nums {
nums[i] = nums[i]*n - sum
}
m := n / 2
left := map[int]bool{}
// 这里使用二进制表示各个位置的数字是否选取，1~ 2的m次方-1个数字可以代表所有前m个数字状态
//，遍历每一个状态组合，求的所有和，
// 如果存在和为0的子集，那么就满足推到中的条件，即返回true，
//反之我们要继续遍历右侧找到左侧是否有与其对应的相反数，如果有左右相加可得0，依然满足推导
for i := 1; i < 1<<m; i++ {
tot := 0
for j, x := range nums[:m] {
if i>>j&1 > 0 {
tot += x
}
}
if tot == 0 {
return true
}
left[tot] = true
}
rsum := 0
for _, x := range nums[m:] {
rsum += x
}
for i := 1; i < 1<<(n-m); i++ {
tot := 0
for j, x := range nums[m:] {
if i>>j&1 > 0 {
tot += x
}
}
if tot == 0 || rsum != tot && left[-tot] {
return true
}
}
return false
}
看过大佬的一些评论，写的比较好，可是自己还是没理解
先说官方题解中的推论，我自己总结起来是，把数组nums分成左右两块，要么左边找到和值为0的组合，要么是左右两边找到和值互为相反的子集。
尤其是在遍历右侧的二进制位时，下边的这些代码不理解
Go
if tot == 0 || rsum != tot && left[-tot] {
return true
}tot==0 这个条件我看意思是右侧一个也没有选择(一个1也没有) ，既然代码已经走到这里了，那么左侧一定是没有存在和为0的情况，在右侧应该找到与左侧互为相反数的子集，可以右侧一个也没选择怎么就返回true了 ？
在看另外一个分支 rsum != tot && left[-tot] ,那 由结论得出左右两边各自找到一个互为相反数的子集也符合条件，left[-tot] 这个还好理解，可是 rsum != tot 这个是啥意思？ 我字面翻译 右侧不能全选，我问了下评论区的大佬，说如果右侧全选了，那么左侧也必须全选，我在看了下题目，也是啊 左右数目各 n/2 ，而且每个数字都得分到A,B数组中，可是我又不理解了，为什么不能出现右边全选，左边也全选呢(即 -lsum +rsum =0) ? 这里的左右不代表A,B么？
评论 (12)
