leetcode：805. 数组的均值分割【meet in middle + 选or不选 + 折半搜索】

题目截图

题目分析

• 分析一下需要SumA / LenA = Sum / Len
• 暴力搜索要n * 2 ^ 30爆炸
• 考虑meet in middle，复杂度变为n * 2 ^ 15
• Sum变为0，可以免去浮点数,nums[i] = nums[i] * n - Sum
• 分成左右两部分left和right
• 先遍历left，如果left中爆搜出0直接结束，否则记录当前和tot入set
• 再遍历right，如果right中爆搜出0直接结束，否则判断-tot是否在left的set中
• 注意：tot不能等于rSum,因为听说这样会导致两方全选，而另一部分为空

ac code

class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        # 折半搜索例题
        # SumA / LenA = Sum / Len
        # 为了方便，变成0的Sum
        n = len(nums)
        s = sum(nums)
        if n == 1:
            return False
        # 很优秀的一步
        for i in range(n):
            nums[i] = nums[i] * n - s # mean = 0
        
        #print(nums)
        # 折半搜索: O(n * 2 ** (n / 2))
        m = n // 2
        # 前半爆搜
        left = set()
        for i in range(1, 1 << m):
            tot = sum(x for j, x in enumerate(nums[:m]) if (i >> j) & 1 == 1)
            if tot == 0:
                return True
            left.add(tot)
        # 后半爆搜
        rSum = sum(nums[m:])
        for i in range(1, 1 << (n - m)):
            tot = sum(x for j, x in enumerate(nums[m:]) if (i >> j) & 1 == 1)
            if tot == 0:
                return True
            # 跟前一半形成相反
            # tot不能为rSum, 否则对应的前面也会取满
            # 真不可能是0... 所以必然会取满
            if -tot in left and tot != rSum:
                return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

总结

• meet in middle解决选or不选过大，但折半可行的状态
• *n的操作去除浮点数，-Sum可以回归到0，比较方便
• 为什么tot == rSum就是全选呢？希望大家可以解答一下5555
• Sum = 0有一大好处，不管lenA怎么变，SumA总是0！