【LeetCode 每日一题】2348. 全 0 子数组的数目
Problem: 2348. 全 0 子数组的数目
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N)
- 空间复杂度：O(1)
整体思路
这段代码的目的是计算一个整数数组 nums 中，所有仅由 0 组成的连续子数组的总数量。例如，对于 [0, 0, 1, 0]，由0组成的子数组有 [0] (第一个), [0] (第二个), [0, 0], [0] (第四个)，总共 4 个。
该算法采用了一种非常高效的 单次遍历（One-Pass） 动态规划思想。它不直接枚举所有子数组，而是通过一个巧妙的增量计算方法来累计总数。
-
核心思想：计算以当前位置为结尾的新增子数组
- 算法的核心不在于寻找一个完整的由0组成的块然后计算其子数组总数（例如，一个长度为 L 的块有
L*(L+1)/2个子数组），而是在遍历过程中，每遇到一个0，就计算有多少个新的、以当前这个0为结尾的、全为0的子数组，并将其累加到总数中。
- 算法的核心不在于寻找一个完整的由0组成的块然后计算其子数组总数（例如，一个长度为 L 的块有
-
关键逻辑与变量
nonZero指针：这个变量是算法的精髓。它始终记录着上一个非零元素出现的位置。ans += i - nonZero：这是算法的核心计算步骤。- 当代码遍历到索引
i，并且nums[i]是0时，i - nonZero的值恰好等于当前连续0串的长度。 - 这个长度也精确地等于以当前
nums[i]为结尾的全零子数组的数量。 - 例如：在
[..., 2, 0, 0, 0]中，nonZero指向2的索引。- 当
i指向第一个0，新增的子数组只有[0]，数量为 1，等于i - nonZero。 - 当
i指向第二个0，新增的子数组有[0]和[0, 0]，数量为 2，等于i - nonZero。 - 当
i指向第三个0，新增的子数组有[0],[0, 0]和[0, 0, 0]，数量为 3，等于i - nonZero。
- 当
- 当代码遍历到索引
-
算法步骤
- 初始化：
ans初始化为 0。nonZero初始化为 -1。这个-1的初始化非常重要，它相当于在数组开始之前有一个“虚拟”的非零元素，这使得从索引 0 开始的连续0串也能被正确计算。 - 遍历：从左到右遍历数组。
- 如果遇到非零元素
x != 0，说明连续的0串中断了。此时更新nonZero的位置为当前索引i。 - 如果遇到零元素
x == 0，则根据上述逻辑，将i - nonZero的值累加到ans中。
- 如果遇到非零元素
- 返回结果：遍历结束后，
ans中就累计了所有全零子数组的总数。
- 初始化：
完整代码
class Solution {/*** 计算数组中所有仅由 0 组成的连续子数组的总数量。* @param nums 输入的整数数组* @return 全零连续子数组的总数*/public long zeroFilledSubarray(int[] nums) {// ans: 用于存储最终结果。使用 long 类型以防止整数溢出，因为子数组数量可能很大。long ans = 0;// nonZero: 一个指针，记录上一个非零元素出现的索引。// 初始化为 -1 是一个关键技巧，它相当于在数组最左边有一个虚拟的非零元素边界，// 使得从索引 0 开始的连续 0 串也能被正确处理。int nonZero = -1;// 遍历数组的每一个元素for (int i = 0; i < nums.length; i++) {int x = nums[i];// 如果当前元素不是 0if (x != 0) {// 那么一个连续的 0 串（如果有的话）到此结束。// 更新 nonZero 的位置到当前索引 i，作为下一个可能的 0 串的左边界。nonZero = i;} else {// 如果当前元素是 0// 'i - nonZero' 计算的是当前连续 0 串的长度。// 这个长度也恰好等于以当前这个 0 为结尾的、新形成的全零子数组的数量。// 例如，对于 [2, 0, 0, 0]，当 i 指向第三个0时, nonZero 指向2。// 长度为3，新增的子数组是 [0], [0,0], [0,0,0]，数量也是3。// 将这个数量累加到总数中。ans += i - nonZero;}}// 返回最终的累计结果return ans;}
}
时空复杂度
时间复杂度：O(N)
- 循环：算法的核心是一个
for循环，它从头到尾遍历nums数组一次。如果数组的长度为N，这个循环将执行N次。 - 循环内部操作：
- 在循环的每一次迭代中，执行的都是基本的比较、赋值和算术运算（加/减）。
- 这些操作的时间复杂度都是 O(1)。
综合分析：
算法由 N 次 O(1) 的操作组成。因此，总的时间复杂度是 N * O(1) = O(N)。
空间复杂度：O(1)
- 主要存储开销：算法只使用了几个固定数量的变量（
ans,nonZero,i,x）来存储状态。 - 空间大小：这些变量的数量不会随着输入数组
nums的大小N而改变。
综合分析：
算法没有使用任何与输入规模 N 成比例的额外数据结构（如新数组或哈希表）。因此，其额外辅助空间复杂度为 O(1)。
参考灵神