Leetcode-6129: number of all 0 subarrays

subject

Topic linking

Give you an array of integers nums , Return all as 0 Of Subarray number .

Subarray Is a sequence of consecutive non empty elements in an array .

Example 1：

 Input ：nums = [1,3,0,0,2,0,0,4]
 Output ：6
 explain ：
 Subarray  [0]  There is  4  Time .
 Subarray  [0,0]  There is  2  Time .
 No length greater than  2  Of all the  0  Subarray , So we go back to  6 .

Example 2：

 Input ：nums = [0,0,0,2,0,0]
 Output ：9
 explain ：
 Subarray  [0]  There is  5  Time .
 Subarray  [0,0]  There is  3  Time .
 Subarray  [0,0,0]  There is  1  Time .
 No length greater than  3  Of all the  0  Subarray , So we go back to  9 .

Example 3：

 Input ：nums = [2,10,2019]
 Output ：0
 explain ： Not all  0  Subarray , So we go back to  0 .

Problem solving

Method 1 ： The sliding window + A sequence of equal differences

Continuous recording 0 Array length of as well as Corresponding to the number of their occurrence
By sliding the window .

Then according to the continuous 0 The length of the array and the number of occurrences , To calculate the total 0 The number of subarrays of .

For example, for [0,0,0]
One 0 The number of by ：3
Two 0 The number of ：2
Three 0 The number of ：1
So it's all 0 The number of subarrays of is (1+3)*3/2
Finally multiply by [0,0,0] The number of occurrences is enough

class Solution {
    
public:
    long long zeroFilledSubarray(vector<int>& nums) {
    
        int n=nums.size();
        unordered_map<int,int> cnt;// Successive 0 Number ----> Number 
        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;


    }
};