LeetCode 1248. Count Number of Nice Subarrays

原题链接在这里：https://leetcode.com/problems/count-number-of-nice-subarrays/

题目：

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

题解：

When runner hits a odd, k--.

While k == 0, move the walker. And count how many steps walker could move it means how many extended even numbers there could be.

e.g. 2, 2, 2, 1, 2, 2, 1, 2, 2. walker could move form 0 to 3 totally 4 steps, which corresponds to subarray with 0 count of 2, 1 count of 2, 2 count of 2 and 3 count of 2. 

Then where ever runner moves one, there could be 4 possible subarrays from the left side.

Time Complexity: O(n). n = nums.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int numberOfSubarrays(int[] nums, int k) {
 3         int n = nums.length;
 4         int res = 0;
 5         int walker = 0;
 6         int runner = 0;
 7         int count = 0;
 8         while(runner < n){
 9             if(nums[runner++] % 2 == 1){
10                 k--;
11                 count = 0;
12             }
13             
14             while(k == 0){
15                 k += nums[walker++] % 2;
16                 count++;
17             }
18             
19             res += count;
20         }
21         
22         return res;
23     }
24 }

类似Count Subarrays With Fixed Bounds.