2348. 全 0 子数组的数目
题目描述
给你一个整数数组 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 <= 105
-109 <= nums[i] <= 109
解法
方法一:遍历计数
我们遍历数组 \(\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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|