leetcode-6129：全 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 。

解题

方法一：滑动窗口+等差数列

记录连续0的数组长度 以及 对应它们出现的个数
通过滑动窗口来实现。

然后根据连续0的数组长度和出现的次数，来计算全0的子数组个数。

比如对于 [0,0,0]
一个0的个数 为：3
两个0的个数为：2
三个0的个数为：1
因此全0的子数组个数为(1+3)*3/2
最后再乘上[0,0,0]出现的次数就行了

class Solution {
    
public:
    long long zeroFilledSubarray(vector<int>& nums) {
    
        int n=nums.size();
        unordered_map<int,int> cnt;//连续的0数量---->个数
        int left=0,right=0;
        while(right<n){
    
            while(left<n&&nums[left]!=0) left++;
            right=left;
            while(right<n&&nums[right]==0) right++;
            cnt[right-left]++;
            left=right;  
        }
        long long res=0;
        for(auto& it:cnt){
    
            res+=(1ll+it.first)*it.first/2 *it.second;
        }
        return res;


    }
};