目录

• 问题描述
• 例子
• 方法一
• 方法二

Leetcode 1248

问题描述

Given an array of integers nums and an integer k. A 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

方法一

** Solution Java **
** 9ms, beats 87.03% **
** 53MB, beats 100.00% **
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        for (int i = 0; i < nums.length; ++i) 
            nums[i] %= 2;
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    private int atMost(int[] nums, int k) {
        if (k < 0) return 0;
        int n = nums.length, res = 0;
        for (int i = 0, j = 0; j < n; ++j) {
            k -= nums[j];
            while (k < 0) 
                k += nums[i++];
            res += j - i + 1;
        }
        return res;
    }
}

方法二

** Solution Java **
** 9ms, beats 87.03% **
** 52.6MB, beats 100.00% **
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length, res = 0, count = 0;
        for (int i = 0, j = 0; j < n; ++j) {
            if (nums[j] % 2 == 1) {
                --k;
                count = 0;
            }
            while (k == 0) {
                k += nums[i++] % 2;
                ++count;
            }
            res += count;
        }
        return res;
    }
}