Medium

题目描述

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

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

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
没有长度超过 2 的全零子数组，所以我们返回 6。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
没有长度超过 3 的全零子数组，所以我们返回 9。

示例 3：

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

提示：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题的核心思想是：对于长度为 n 的连续零序列，它能构成 1 + 2 + … + n = n * (n + 1) / 2 个全零子数组。

解题思路

  1. 一次遍历法（推荐）：遍历数组，维护当前连续零的长度。每遇到一个零，以该零结尾的全零子数组数量就是当前连续零的长度。

  2. 分段计算法：找出所有连续零的段，对每段计算子数组数量并累加。

以示例1为例：[1,3,0,0,2,0,0,4]

  • 第一段连续零：[0,0]，长度2，贡献 2*(2+1)/2 = 3 个子数组
  • 第二段连续零：[0,0]，长度2，贡献 2*(2+1)/2 = 3 个子数组
  • 总计：3 + 3 = 6

推荐使用一次遍历法，它更直观且效率更高。关键在于理解：当我们遇到第 k 个连续的零时，以这个零结尾的全零子数组有 k 个（分别是长度为1, 2, …, k的子数组）。

代码实现

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long result = 0;
        long long consecutiveZeros = 0;
        
        for (int num : nums) {
            if (num == 0) {
                consecutiveZeros++;
                result += consecutiveZeros;
            } else {
                consecutiveZeros = 0;
            }
        }
        
        return result;
    }
};

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

public class Solution {
    public long ZeroFilledSubarray(int[] nums) {
        long result = 0;
        long consecutiveZeros = 0;
        
        foreach (int num in nums) {
            if (num == 0) {
                consecutiveZeros++;
                result += consecutiveZeros;
            } else {
                consecutiveZeros = 0;
            }
        }
        
        return result;
    }
}

var zeroFilledSubarray = function(nums) {
    let count = 0;
    let consecutive = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            consecutive++;
            count += consecutive;
        } else {
            consecutive = 0;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用了常数额外空间

相关题目