题目

给你一个整数数组 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^5
-109 <= nums[i] <= 10^9

解题思路

核心思想是识别出数组中所有连续的、由 0 组成的片段（或称为“全零子数组块”），并分别计算每个片段能构成多少个全零子数组，最后将所有片段的结果累加起来，就是最终答案。

具体步骤如下：

遍历数组：从头到尾扫描整个输入数组 nums。
寻找并计量连续的零：
- 在遍历过程中，使用一个计数器来记录当前连续遇到的 0 的个数。
- 当遇到一个非零元素时，或者当遍历到数组末尾时，就意味着一个连续的零片段结束了。
计算单个片段的子数组数量：
- 对于一个长度为 k 的连续零片段（例如 [0, 0, ..., 0]，共 k 个 0），它所能构成的全零子数组的数量是一个有规律的数学问题。
- 长度为 1 的子数组 [0] 有 k 个。
- 长度为 2 的子数组 [0, 0] 有 k-1 个。
- ...
- 长度为 k 的子数组 [0, 0, ..., 0] 有 1 个。
- 因此，总数为 k + (k-1) + ... + 1。这个求和公式的结果是 k * (k + 1) / 2。
累加结果：
- 每当一个连续的零片段结束时，就利用上述公式 k * (k + 1) / 2 计算出这个片段贡献的子数组总数，并将其累加到一个最终的总结果变量中。
- 计算完毕后，需要将用于记录连续零个数的计数器重置为 0，以便开始寻找下一个连续的零片段。
返回总和：遍历完整个数组后，累加的总结果就是题目所求的答案。

具体代码

class Solution {
public:
    /**
     * @brief 计算数组中全为 0 的子数组数目。
     *
     * 核心思路：
     * 1. 遍历数组，寻找由 0 组成的连续片段。
     * 2. 每当遇到一个非零数或到达数组末尾时，就意味着一个连续的 0 片段结束了。
     * 3. 对于一个长度为 k 的连续 0 片段，它可以构成的全零子数组数量为 1 + 2 + ... + k，
     * 这个总和可以用数学公式 k * (k + 1) / 2 计算得出。
     * 4. 将每个连续 0 片段计算出的子数组数量累加起来，就是最终的结果。
     */
    long long zeroFilledSubarray(vector<int>& nums) {
        int n = nums.size(); // 获取数组的长度
        
        // 'num' 用于记录当前连续 0 的个数（即当前 0 片段的长度）
        long long num = 0; 
        
        // 'result' 用于累加所有全零子数组的总数
        long long result = 0;

        // 遍历整个数组
        for(int i = 0; i < n; i++)
        {
            // 情况一：如果当前元素是 0
            if(nums[i] == 0)
            {
                // 增加当前连续 0 的计数
                num++;
                
                // 边界情况处理：如果当前是数组的最后一个元素
                // 那么循环即将结束，需要在这里结算最后这个连续的 0 片段
                if(i == n - 1) {
                    result += num * (num + 1) / 2;
                }
            }
            // 情况二：如果当前元素不是 0，说明连续的 0 片段在此处中断
            else
            {
                // 结算刚刚结束的那个连续 0 片段
                // 一个长度为 'num' 的连续 0 片段可以构成 num * (num + 1) / 2 个全零子数组
                result += num * (num + 1) / 2;
                
                // 因为 0 片段中断了，所以将计数器重置为 0
                num = 0;
            }
        }

        // 返回累加的总结果
        return result;
    }
};

优化思路

我们可以不等到一个连续的 0 片段结束才去计算它的子数组总数，而是在遍历过程中实时累加。

当我们遇到第1个连续的 0 时，我们新增了 1 个全零子数组：[0]。
当我们紧接着遇到第2个连续的 0 时，我们新增了 2 个以它结尾的全零子数组：[0, 0] 和 [0]。
当我们遇到第3个连续的 0 时，我们新增了 3 个以它结尾的全零子数组：[0, 0, 0]、[0, 0] 和 [0]。
...
当我们遇到第 k 个连续的 0 时，我们新增了 k 个以它结尾的全零子数组。

所以，我们只需要一个变量来记录当前连续 0 的长度。每当遇到一个 0，我们就把这个长度累加到最终结果中。如果遇到非 0 数，就把这个长度计数器清零。

这个方法巧妙地将 1 + 2 + ... + k 的计算分解到了每一步中，从而避免了在片段结束时使用 k * (k + 1) / 2 公式，也无需任何特殊边界判断。

优化代码

class Solution {
public:
    /**
     * @brief 计算数组中全为 0 的子数组数目（优化版）。
     *
     * 优化思路（增量计算）：
     * 1. 遍历数组，用一个计数器 `current_streak` 记录当前连续 0 的长度。
     * 2. 如果遇到 0，则 `current_streak` 加 1。这个新遇到的 0 会与前面 `current_streak - 1` 个 0
     * 一起构成 `current_streak` 个新的、以当前位置结尾的全零子数组。因此将 `current_streak` 的值累加到结果中。
     * 3. 如果遇到非 0，则连续的 0 片段中断，将 `current_streak` 重置为 0。
     * 4. 这种方法在每一步都进行累加，逻辑更统一，无需在循环结束后或遇到非零数时进行特殊的“结算”操作。
     */
    long long zeroFilledSubarray(vector<int>& nums) {
        // 'result' 用于累加所有全零子数组的总数
        long long result = 0;
        
        // 'current_streak' 用于记录当前连续 0 的长度
        long long current_streak = 0;

        // 遍历数组中的每一个数字
        for (int num : nums) {
            if (num == 0) {
                // 如果是 0，连续长度加 1
                current_streak++;
            } else {
                // 如果不是 0，连续状态中断，长度归零
                current_streak = 0;
            }
            // 将当前连续 0 的长度累加到结果中
            // 例如，当连续长度增长到 3 时，意味着我们找到了 3 个以当前 0 结尾的新子数组
            // 所以，前三次累加的值分别是 1, 2, 3，总和为 6，
            // 这恰好等于一个长度为 3 的片段所能构成的子数组总数。
            result += current_streak;
        }

        return result;
    }
};

2348. 全 0 子数组的数目

beautifulremi

题目

解题思路

具体代码

优化思路

优化代码