Leetcode discuss: 1248. Count Number of Nice Subarrays

 Here is the link. 

Second practice - C# - slide window - less than K

Nov. 4, 2020
Introduction
I like to spend 10 minutes to talk about importance to learn to write a simple and elegant solution from lee215. The algorithm can be solved using slide window, and it should take less than 10 minutes.

Slide window
I like to copy the idea using slide window to solve the problem. Here is lee215's solution. I will write down more analysis to make it more clear.

First it is to convert k odd number to another problem using less than k.
Second is to calculate the array with less than k odd number, how many subarrays? For example, [1, 2, 3, 4], k = 2.

public class Solution {
    public int NumberOfSubarrays(int[] A, int k) {
        return atMost(A, k) - atMost(A, k - 1);
    }

    public int atMost(int[] A, int k) {
        var result = 0;
        var left = 0;
        var n = A.Length;
        
        for (int right = 0; right < n; right++) 
        {
            k -= A[right] % 2;
            
            while (k < 0)
            {
                k += A[left] % 2;
                left++;
            }
            
            result += right - left + 1;
        }
        
        return result;
    }
}