Description
給定整數陣列
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#
核心思路：連續
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)#
- 概念: 找出每段連續 0 的長度
k，用公式k*(k+1)/2累加 - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
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)#
- 概念: 維護當前連續 0 的長度
count，每遇到一個 0 就count++並將count累加到結果（第 k 個 0 新增 k 個子陣列） - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
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
}
}為什麼每個新 0 貢獻
count個子陣列？因為以當前位置為結尾的全零子陣列有count個（長度分別為 1, 2, …, count，但這裡只新增長度為 1 到 count 中以當前 0 結尾的那個）。實際上每個 0 作為新的結尾，恰好新增count個以它結尾的全零子陣列。
🔑 Takeaways#
- Pattern: 連續子陣列計數 -> Running Count 累加
- 關鍵技巧: 「以當前元素結尾」的思維方式：第 k 個連續 0 作為結尾新增 k 個子陣列。這個模式適用於很多「計數特定子陣列」的問題