[leetcode 1248] 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

 

- k개의 홀수를 가진 수열이 나올 때까지 수를 체크(odd++)

- 동시에 홀수가 등장하기 전 수열의 길이를 저장

- 새로운 홀수 수열이 등장할 때까지 전수열의 길이를 더한다.

2 2 2 1 2 2 1 2 2 2

-> 1 2 2 1 전에 붙을 수 있는 수열 ( ), (2), (22), (222) 4가지

-> 12212에 붙는 수열 4가지, 122122에 붙는 4가지 ... 

-> count += prefix[odd-m]

 

 

코드

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        
       vector<int> prefix(nums.size(), 0);
        
        int odd = 0,result=0;
        
        for(int i=0; i<nums.size(); i++){
            prefix[odd]++;
            
            if(nums[i] & 1){
                odd++;
            }
            
            if(odd>=k){
                result += prefix[odd-k];
            }
        }
        
        return result;
    }
};