2348. Number of Zero-Filled Subarrays

題意

給定一個數字陣列，找出所有元素只含有 0 的 subarray 個數

限制

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

解題思路

思考 00000：

• 0 ⇒ 1
• 00 ⇒ 00 + _0 ⇒ 2
• 000 ⇒ 000 + _00 + __0 ⇒ 3

以此類推，一個長度為 n 的連續 0 陣列，其只包含 0 的子陣列數量總和為 $$sum_{i=1}^n i $$，也就是 n(n+1)/2。

Coding流程

• 遍歷陣列：
  • 遇到 0，則開始計算連續 0 的數量，並持續將當前計數加到答案中（會從 1 + 2 + 3 … 累加到最後一個 0）。
  • 遇到非 0 則將連續 0 的記數歸 0。

Solution

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

時間與空間複雜度

• 時間複雜度：整個演算法只需要一次遍歷即可完成，故為 O(n)。
• 空間複雜度：只使用到常數級的變數來計算連續 0 的次數與總和，故為 O(1)。