Welcome to Subscribe On Youtube

1248. Count Number of Nice Subarrays

Description

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

 

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

 

Constraints:

  • 1 <= nums.length <= 50000
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

Solutions

Solution 1: Prefix Sum + Array or Hash Table

The problem asks for the number of subarrays that contain exactly $k$ odd numbers. We can calculate the number of odd numbers $t$ in each prefix array and record it in an array or hash table $cnt$. For each prefix array, we only need to find the number of prefix arrays with $t-k$ odd numbers, which is the number of subarrays ending with the current prefix array.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $nums$.

  • class Solution {
        public int numberOfSubarrays(int[] nums, int k) {
            int n = nums.length;
            int[] cnt = new int[n + 1];
            cnt[0] = 1;
            int ans = 0, t = 0;
            for (int v : nums) {
                t += v & 1;
                if (t - k >= 0) {
                    ans += cnt[t - k];
                }
                cnt[t]++;
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int numberOfSubarrays(vector<int>& nums, int k) {
            int n = nums.size();
            vector<int> cnt(n + 1);
            cnt[0] = 1;
            int ans = 0, t = 0;
            for (int& v : nums) {
                t += v & 1;
                if (t - k >= 0) {
                    ans += cnt[t - k];
                }
                cnt[t]++;
            }
            return ans;
        }
    };
    
  • class Solution:
        def numberOfSubarrays(self, nums: List[int], k: int) -> int:
            cnt = Counter({0: 1})
            ans = t = 0
            for v in nums:
                t += v & 1
                ans += cnt[t - k]
                cnt[t] += 1
            return ans
    
    
  • func numberOfSubarrays(nums []int, k int) (ans int) {
    	n := len(nums)
    	cnt := make([]int, n+1)
    	cnt[0] = 1
    	t := 0
    	for _, v := range nums {
    		t += v & 1
    		if t >= k {
    			ans += cnt[t-k]
    		}
    		cnt[t]++
    	}
    	return
    }
    
  • function numberOfSubarrays(nums: number[], k: number): number {
        const n = nums.length;
        const cnt = new Array(n + 1).fill(0);
        cnt[0] = 1;
        let ans = 0;
        let t = 0;
        for (const v of nums) {
            t += v & 1;
            if (t - k >= 0) {
                ans += cnt[t - k];
            }
            cnt[t] += 1;
        }
        return ans;
    }
    
    

All Problems

All Solutions