题目描述

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

样例1

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

样例2

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

样例3

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

算法1

(前缀和+哈希表) $O(n)$

• 先用前缀和计算出$s[i]$：前i个数中奇数的个数
• 区间[i,j]中奇数个数为：$s[j]-s[i-1]$
• 问题转化为：挑选出所有区间[i,j]使得$s[j]-s[i-1]=k$，这其实就是经典的两数之和问题
• $s[j]-k=s[i-1]$：$i-1$在$j$前面出现，所以每次循环判断$s[j]-k$在不在哈希表中，如果在，则说明出现满足条件的数组了
• 注意：可能有哈希表元素频次大于1的情况，说明子数组可能重复：例如[1,1,1]和[1,1,1,2]和[1,1,1,2,2]，k=3

Java 代码

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        //s[i]表示i个数内有多少个奇数
        int[] s = new int[n+1];
        s[0] = 0;
        for(int i = 1; i <= n; i++) s[i] = s[i-1]+(nums[i-1] & 1);

        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i <= n; i++){
            int x = s[i]-k;
            if(map.containsKey(x)) res += map.get(x);
            map.put(s[i],map.getOrDefault(s[i],0)+1);
        }
        return res;
    }
}

• 优化代码

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        //s[i]表示i个数内有多少个奇数
        int[] s = new int[n+1];
        int[] map = new int[n+1];
        s[0] = 0;
        for(int i = 0; i <= n; i++){
            if(i > 0) s[i] = s[i-1]+(nums[i-1] & 1);
            res += s[i]-k >= 0 ? map[s[i]-k] : 0;
            map[s[i]]++;
        }
        return res;
    }
}