給你一個整數數組 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 <= 105^55
-109^99 <= nums[i] <= 109^99
分組循環,找出全0的一組,并計算子數組數量:
class Solution {
public:long long zeroFilledSubarray(vector<int>& nums) {int n = nums.size();long long ans = 0;int i = 0;while (i < n) {if (nums[i] != 0) {++i;continue;}int start = i;while (i < n && nums[i] == 0) {++i;}int len = i - start;ans += (long long)len * (len + 1) / 2;}return ans;}
};
如果nums的長度為n,則此算法時間復雜度為O(n),空間復雜度為O(1)。