What is the main pattern for solving the 'Number of Zero-Filled Subarrays' problem?

The main pattern involves recognizing that each zero contributes to multiple subarrays, with consecutive zeros forming increasing numbers of subarrays as you progress through the array.

How do I calculate the number of zero-filled subarrays?

For each zero, track the number of consecutive zeros up to that point. The number of zero-filled subarrays ending at that position is equal to the number of consecutive zeros seen so far.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array. This is because the solution involves a single pass through the array.

Can this problem be solved without extra space?

Yes, by keeping a running count of the consecutive zeros, the problem can be solved with O(1) extra space.

What are some common mistakes when solving this problem?

A common mistake is not resetting the consecutive zero count after encountering a non-zero element, or using a brute force method that leads to inefficient solutions.

#2348

Medium

auto_awesome数组·数学

LeetCode 题解工作台

全 0 子数组的数目

给你一个整数数组 nums ，返回全部为 0 的子数组数目。子数组是一个数组中一段连续非空元素组成的序列。示例 1：输入： nums = [1,3,0,0,2,0,0,4] 输出： 6 解释：子数组 [0] 出现了 4 次。子数组 [0,0] 出现了 2 次。不存在长度大于 2 的…

数组数学

题目描述

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

提示：

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：遍历计数

我们遍历数组 $\textit{nums}$ ，用变量 $\textit{cnt}$ 记录当前连续的 $0$ 的个数。那么对于当前遍历到的元素 $x$ ，如果 $x$ 为 $0$ ，则 $\textit{cnt}$ 自增 $1$ ，以当前 $x$ 为结尾的全 $0$ 子数组的个数为 $\textit{cnt}$ ，将其累加到答案中。否则，我们将 $\textit{cnt}$ 置为 $0$ 。

遍历结束后，返回答案即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

相似题目：

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = cnt = 0
        for x in nums:
            if x == 0:
                cnt += 1
                ans += cnt
            else:
                cnt = 0
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate recognizes the need to count consecutive zeros efficiently.
question_mark
The candidate can optimize space usage while keeping the time complexity linear.
question_mark
The candidate avoids brute force and handles large input sizes effectively.

warning

常见陷阱

外企场景

error
Forgetting to reset the consecutive zero count after encountering a non-zero element.
error
Underestimating the total number of subarrays when multiple consecutive zeros appear.
error
Using nested loops to check for zero subarrays, leading to inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to count subarrays filled with ones instead of zeros.
arrow_right_alt
Consider a similar problem but with non-zero elements where you count subarrays with sums equal to a target value.
arrow_right_alt
Extend the problem to multidimensional arrays, counting subarrays in a 2D matrix.

help

常见问题

外企场景

继续练习

#2344 使数组可以被整除的最少删除次数 #2358 分组的最大数量 #2364 统计坏数对的数目