1248. 统计优美子数组

给你一个整数数组 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，偶数置为0
for (int i = 0; i < nums.length; i++) {
    if (nums[i]%2 == 0) {
        nums[i] = 0;
    } else {
        nums[i] = 1;
    }
}

那么题目就变成 560. 和为 K 的子数组

public int numberOfSubarrays(int[] nums, int k) {
    // 将数组中奇数置为1，偶数置为0
    for (int i = 0; i < nums.length; i++) {
        if (nums[i]%2 == 0) {
            nums[i] = 0;
        } else {
            nums[i] = 1;
        }
    }
    // 问题变为求解和为 K 的子数组
    int count = 0;
    // 外层循环控制子数组最大长度
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        // 内层循环计算是否存在子数组的和满足要求
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum == k) {
                count++;
            }
        }
    }
    return count;
}

利用前缀和

public int numberOfSubarrays(int[] nums, int k) {
    // 将数组中奇数置为1，偶数置为0
    for (int i = 0; i < nums.length; i++) {
        if (nums[i]%2 == 0) {
            nums[i] = 0;
        } else {
            nums[i] = 1;
        }
    }
    // 问题变为求解和为 K 的子数组
    // 前缀和数组
    int[] sums = new int[nums.length+1];
    for (int i = 0; i < nums.length; i++) {
        // 这里需要注意，前缀和是从 presum[1]开始填充的
        sums[i + 1] = sums[i] + nums[i];
    }
    // 统计 sums 中两个元素的差 等于 k 的次数
    int count = 0;
    for (int i = 0; i < sums.length - 1; i++) {
        for (int j = i; j < sums.length - 1; j++) {
            if (sums[j + 1] - sums[i] == k) {
                count++;
            }
        }
    }
    return count;
}

前缀和+哈希

public int numberOfSubarrays(int[] nums, int k) {
    // 将数组中奇数置为1，偶数置为0
    for (int i = 0; i < nums.length; i++) {
        if (nums[i]%2 == 0) {
            nums[i] = 0;
        } else {
            nums[i] = 1;
        }
    }
    // 问题变为求解和为 K 的子数组
    if (nums.length == 0) {
        return 0;
    }
    int count = 0;
    HashMap<Integer,Integer> map = new HashMap<>();
    // 细节，这里需要预存前缀和为 0 的情况
    map.put(0, 1);
    int presum = 0;
    for (int x : nums) {
        presum += x;
        // 当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
        if (map.containsKey(presum - k)) {
            // 累加次数
            count += map.get(presum - k);
        }
        // 更新
        map.put(presum, map.getOrDefault(presum,0) + 1);
    }
    return count;
}

public int numberOfSubarrays(int[] nums, int k) {
    // 将数组中奇数置为1，偶数置为0
    for (int i = 0; i < nums.length; i++) {
        if (nums[i]%2 == 0) {
            nums[i] = 0;
        } else {
            nums[i] = 1;
        }
    }
    return subarraySum(nums, k);
}
public int subarraySum(int[] nums, int k) {
    if (nums.length == 0) {
        return 0;
    }
    int count = 0;
    HashMap<Integer,Integer> map = new HashMap<>();
    map.put(0, 1);
    int presum = 0;
    for (int x : nums) {
        presum += x;
        if (map.containsKey(presum - k)) {
            count += map.get(presum - k);
        }
        map.put(presum, map.getOrDefault(presum,0) + 1);
    }
    return count;
}