【LeetCode 每日一题】2348. 全 0 子数组的数目

Problem: 2348. 全 0 子数组的数目

整体思路

这段代码的目的是计算一个整数数组 nums 中，所有仅由 0 组成的连续子数组的总数量。例如，对于 [0, 0, 1, 0]，由0组成的子数组有 [0] (第一个), [0] (第二个), [0, 0], [0] (第四个)，总共 4 个。

该算法采用了一种非常高效的 单次遍历（One-Pass） 动态规划思想。它不直接枚举所有子数组，而是通过一个巧妙的增量计算方法来累计总数。

1. 核心思想：计算以当前位置为结尾的新增子数组

   • 算法的核心不在于寻找一个完整的由0组成的块然后计算其子数组总数（例如，一个长度为 L 的块有 L*(L+1)/2 个子数组），而是在遍历过程中，每遇到一个 0，就计算有多少个新的、以当前这个 0 为结尾的、全为0的子数组，并将其累加到总数中。

2. 关键逻辑与变量

   • 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。

3. 算法步骤

   • 初始化：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];
            // 如果当前元素不是 0
            if (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)

1. 循环：算法的核心是一个 for 循环，它从头到尾遍历 nums 数组一次。如果数组的长度为 N，这个循环将执行 N 次。
2. 循环内部操作：
   • 在循环的每一次迭代中，执行的都是基本的比较、赋值和算术运算（加/减）。
   • 这些操作的时间复杂度都是 O(1)。

综合分析：
算法由 N 次 O(1) 的操作组成。因此，总的时间复杂度是 N * O(1) = O(N)。

空间复杂度：O(1)

1. 主要存储开销：算法只使用了几个固定数量的变量（ans, nonZero, i, x）来存储状态。
2. 空间大小：这些变量的数量不会随着输入数组 nums 的大小 N 而改变。

综合分析：
算法没有使用任何与输入规模 N 成比例的额外数据结构（如新数组或哈希表）。因此，其额外辅助空间复杂度为 O(1)。

参考灵神