1 比 0 多的子数组个数

Submission

运行时间: 107 ms

内存: 21.3 MB

class Solution:
    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:
        M = 1_000_000_007
        cnts = [0] * (2 * len(nums) + 1)
        cnts[0] = 1
        ans = cnt = s = 0
        for num in nums:
            if num:
                cnt += cnts[s]
                s += 1
            else:
                s -= 1
                cnt -= cnts[s]
            cnts[s] += 1
            ans = (ans + cnt) % M
        return ans

Explain

该题解使用前缀和的思路来解决问题。通过维护一个前缀和数组 cnts，其中 cnts[i] 表示前缀和为 i 的子数组个数。遍历数组 nums，对于每个元素，如果是 1，则将前缀和加 1；如果是 0，则将前缀和减 1。对于当前前缀和 s，cnt 变量累加 cnts[s]，表示以当前元素结尾、满足条件的子数组个数。最后将 cnt 累加到答案 ans 中，并对 10^9 + 7 取模。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def subarraysWithMoreZerosThanOnes(self, nums: List[int]) -> int:
        M = 1_000_000_007
        cnts = [0] * (2 * len(nums) + 1)  # 初始化前缀和数组
        cnts[0] = 1  # 前缀和为 0 的子数组个数初始化为 1
        ans = cnt = s = 0
        for num in nums:
            if num:
                cnt += cnts[s]  # 累加以当前元素结尾、满足条件的子数组个数
                s += 1  # 更新前缀和
            else:
                s -= 1  # 更新前缀和
                cnt -= cnts[s]  # 减去以当前元素结尾、不满足条件的子数组个数
            cnts[s] += 1  # 更新前缀和为 s 的子数组个数
            ans = (ans + cnt) % M  # 将 cnt 累加到答案中，并取模
        return ans

Explore

在题解中，前缀和数组 cnts 的大小被设置为 2 * len(nums) + 1，这是为了确保即使前缀和为负数，也能在数组中正确索引。前缀和数组的中间索引（len(nums)）代表前缀和为0的位置。当前缀和为正时，索引为 len(nums) + s；当前缀和为负时，索引为 len(nums) - |s|。这种映射方法允许我们在同一数组中处理正数和负数前缀和，避免了使用哈希表等其他更复杂的数据结构。

在题解的逻辑中，当元素为0时，前缀和 s 减 1，这意味着我们正在探索尾部含有更多0的子数组。在这种情况下，我们需要从 cnt 中减去 cnts[s]，因为 cnts[s] 记录的是以当前 s 为前缀和的子数组个数，这个操作是为了剔除那些不满足“1比0多”的子数组计数。简而言之，这是为了确保 cnt 变量仅包括满足题目要求的子数组数，从而准确地统计符合条件的子数组。

取模操作通常用于处理大数运算，以防止整数溢出并减小处理数的规模。在许多编程比赛和实际应用中，答案很大时常常要求对一个大的质数（如 10^9 + 7）取模，以保持结果的可管理性并避免数据类型的限制。在本题中，使用取模操作是为了确保计算过程中和结果的数值不会超出编程语言处理整数的范围，同时满足可能的输出要求。

在题解中，前缀和 s 根据当前遍历的元素更新：如果是1，则 s 增加1；如果是0，则 s 减少1。这种更新方式直接关联到子数组的计数，因为它反映了从数组开始到当前元素的1和0的净差值。前缀和的变化用于识别数组中1比0多的部分，通过前缀和数组 cnts 记录和追踪特定前缀和值出现的次数，从而计算满足条件的子数组个数。每次 s 更新后，通过 cnts[s] 的值可以直接得知当前前缀和值对应的子数组数量，这是计算满足条件子数组的核心逻辑。