[LeetCode 2348] Number of Zero-Filled Subarrays

문제 바로가기

Description

---

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 <= 10^5
• -10^9 <= nums[i] <= 10^9

Hint

---

Hint 1

  For each zero, you can calculate the number of zero-filled subarrays that end on that index, which is the number of consecutive zeros behind the current element + 1.
	

Hint 2

  Maintain the number of consecutive zeros behind the current element, count the number of zero-filled subarrays that end on each index, sum it up to get the answer.
	

Code

---

내 제출

---

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long ans = 0;
        int cnt = 0;
        for (int x : nums) {
            if (x == 0) {
                ans += ++cnt;
            } else {
                cnt = 0;
            }
        }
        return ans;
    }
}

Runtime	Memory
3 ms	61.4 MB

다른 풀이

---

class Solution {
    public long zeroFilledSubarray(int[] nums) {
		int n = nums.length;
	    long sol =0;
	    long count =0 ;
	    for(int i =0 ; i < n ;i++) {
		    if (nums[i] == 0) {
				count++;
				sol += count;
			} else {
				count = 0;
			}
		}
		return sol; 
	} 
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2300-2399/2348.Number%20of%20Zero-Filled%20Subarrays/Solution.java