給定整數陣列
nums，回傳所有元素全為 0 的子陣列數量。
Example:
Input: nums = [1,3,0,0,2,0,0,4] Output: 6 （[0], [0], [0,0], [0], [0], [0,0] 共 6 個全零子陣列）
Intuition
TIP
核心思路：連續 k 個 0 會產生 k*(k+1)/2 個全零子陣列。遍歷陣列計算每段連續 0 的長度即可。
- 等價於：對每段連續 0 的長度
k，貢獻1 + 2 + ... + k = k*(k+1)/2 - 也可以邊遍歷邊累加：每遇到一個 0，它能與前面的連續 0 組成的子陣列數等於目前連續 0 的長度
Approaches
1. Count Consecutive Zeros (Segment) — O(n) / O(1)
- Idea: 找出每段連續 0 的長度
k，用公式k*(k+1)/2累加 - Time:
O(n)- 一次遍歷 - Space:
O(1)- 常數空間
class Solution {
fun zeroFilledSubarray(nums: IntArray): Long {
var result = 0L
var consecutive = 0L
for (num in nums) {
if (num == 0) {
consecutive++
} else {
result += consecutive * (consecutive + 1) / 2
consecutive = 0
}
}
result += consecutive * (consecutive + 1) / 2
return result
}
}⭐ 2. Running Count (One-Pass) — O(n) / O(1)
- Idea: 維護當前連續 0 的長度
count，每遇到一個 0 就count++並將count累加到結果（第 k 個 0 新增 k 個子陣列） - Time:
O(n)- 一次遍歷 - Space:
O(1)- 常數空間
class Solution {
fun zeroFilledSubarray(nums: IntArray): Long {
var result = 0L
var count = 0L
for (num in nums) {
if (num == 0) {
count++
result += count
} else {
count = 0
}
}
return result
}
}WARNING
為什麼每個新 0 貢獻 count 個子陣列？因為以當前位置為結尾的全零子陣列有 count 個（長度分別為 1, 2, …, count，但這裡只新增長度為 1 到 count 中以當前 0 結尾的那個）。實際上每個 0 作為新的結尾，恰好新增 count 個以它結尾的全零子陣列。
🔑 Takeaways
- Pattern: 連續子陣列計數 -> Running Count 累加
- Key trick: 「以當前元素結尾」的思維方式：第 k 個連續 0 作為結尾新增 k 個子陣列。這個模式適用於很多「計數特定子陣列」的問題