Last Updated on 2023-03-21 by Clay
題目
Given an integer array nums, return the number of subarrays filled with 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,3,0,0,2,0,0,4] Output: 6 Explanation: There are 4 occurrences of [0] as a subarray. There are 2 occurrences of [0,0] as a subarray. There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.
Example 2:
Input: nums = [0,0,0,2,0,0] Output: 9 Explanation: There are 5 occurrences of [0] as a subarray. There are 3 occurrences of [0,0] as a subarray. There is 1 occurrence of [0,0,0] as a subarray. There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.
Example 3:
Input: nums = [2,10,2019] Output: 0 Explanation: There is no subarray filled with 0. Therefore, we return 0.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109
題目給定一個數值陣列的輸入，我們要做的就是計算 0 的子陣列出現的次數並回傳。像是如果陣列中出現了 [0, 0, 0]，就代表著 [0] 出現了 3 次、[0, 0] 出現了 2 次、[0, 0, 0] 出現了 1 次。
解題思路
想必大家很快就會發現，只要計算出連續的 0 出現次數，就可以輕易推算出底下到底包含多少個 0 的子陣列。舉例來說，如果 0 出現了 4 次，代表著 0 出現 3 次的子陣列可以滑動一次，所以有『兩個』0 出現 3 次的子陣列...... 依此類推，結論就是 0 連續出現 4 次的子陣列總共是 4 + 3 + 2 + 1 = 10。
- [0, 0, 0, 0] 出現 1 次
- [0, 0, 0] 出現 2 次
- [0, 0] 出現 3 次
- [0] 出現 4 次
所以我們只需要一路掃過去並計算 0 的連續出現次數，一路增加累加值，並在碰到非 0 時即時將累加值初始化為 1 即可。
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
// Init
long long results = 0;
long long accum = 1;
// Accumulate
for (int num: nums) {
if (num == 0) {
results += accum;
++accum;
}
else {
accum = 1;
}
}
return results;
}
};Python 範例程式碼
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
# Init
results = 0
accum = 1
# Accumulate
for num in nums:
if num == 0:
results += accum
accum += 1
else:
accum = 1
return results