連結

2348. Number of Zero-Filled Subarrays
https://leetcode.com/problems/number-of-zero-filled-subarrays/

想法

1.使用一個計數器去存放出現 0 的次數
2.我們只要同時檢查 N 個 0 在之中就加一

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def zeroFilledSubarray(self, nums):
        counter = 0
        nums_ = nums
        for index, value in enumerate(nums_):
            if 0 == value:
                counter += 1
                if index-1 >= 0 and 0 == nums_[index-1]:
                    counter += 1
                    if index-2 >= 0 and 0 == nums_[index-2]:
                        counter += 1
                        # ...... 不斷的檢查前面有沒有 0
        return counter

之後透過使用 for 的方式解決，有這樣的方式是可行的，但因為有兩個 for 時間效率不高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def zeroFilledSubarray(self, nums):
        counter = 0
        for index, value in enumerate(nums):
            if 0 == value:
                counter += 1
                # 使用 for 的方式合併全部 if
                for i in range(index+1):
                    if 0 == i:
                        pass
                    elif 0 == nums[index-i]:
                        counter += 1
                    else:
                        break
        return counter
  • 出現 Time Limit Exceeded 錯誤
    Input：[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,………..,0,0,0]
    Output：算太久了~ 沒有 Output

神人解答

之後我先看了解答後發現可以做想法的修正，但由於解答使用簡單的語法就完成了，於是我就不再修改我的程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def zeroFilledSubarray(self, nums):
        total_zero_subarrays = current_zero_subarrays = 0
                
        for num in nums:
            if num == 0:
                # 若上一個元素是零，則繼續累積 (1+2+3+4....)
                current_zero_subarrays += 1
                # 並且讓 total 去加上這個已累積的值
                total_zero_subarrays += current_zero_subarrays
            else:
                # 若上一個元素不是零，就不用累積，並歸 0
                current_zero_subarrays = 0
                
        return total_zero_subarrays