LeetCode.1248.Count Number of Nice Subarrays 统计优美子数组

题目描述

1248 Count Number of Nice Subarrays
https://leetcode-cn.com/problems/count-number-of-nice-subarrays/

给你一个整数数组 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 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

---

相似题目

LeetCode.1248.Count Number of Nice Subarrays 统计优美子数组
LeetCode.560.Subarray Sum Equals K 和为K的子数组
LeetCode.974.Subarray Sums Divisible by K 和可被K整除的子数组
523 连续的子数组和
https://leetcode-cn.com/problems/continuous-subarray-sum/

---

解题过程

O(n)前缀和+哈希Map

可以这样思考，奇数转为 1, 偶数转为 0, 然后求和为 k 的子数组个数。
这里的前缀和 sum[i] 是前 i 个数中的奇数的个数，或者这样理解，奇数转为1，偶数转为0之后的前缀和

参考题目

560 和为K的子数组
https://leetcode-cn.com/problems/subarray-sum-equals-k/

用前缀和+哈希做
参考题解
https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/qian-zhui-he-hash-xiang-xi-zhu-shi-yi-kan-jiu-dong/

O(n)统计奇数前后的偶数个数

找到第 i 个奇数的位置，找到第 i+k-1 个奇数的位置，则这两个奇数之间的元素组成的子数组中的奇数个数肯定是k，这就确定了两个边界，再看这两个边界的活动范围有多大就知道有几种组合了。
统计左边界也就是第 i 个奇数 和 第 i-1 个奇数之间的偶数个数 leftCount，右边界也就是第 i+k-1 个奇数 和 第 i+k 个奇数之间的偶数个数 rightCount，则共有 (leftCount+1) × (rightCount+1) 种子数组的组合其奇数个数都是 k，其中加 1 的原因是还要包括 i 和 i+k-1 本身，所以 i 开头的这个奇数个数为 k 的子数组通过左右边界扩展可贡献 (leftCount+1) × (rightCount+1) 个奇数个数为k的子数组。
(上一个奇数位置 到 当前奇数位置的偶数个数) × (当前位置+k-1个奇数 到 其下一个奇数之间的偶数个数) = 当前位置开头的子数组通过扩展可贡献的子数组个数

例1
[2,2,1,1,2,2,2] k = 2
下标 i=3 开始的子数组 1,1 构成一个奇数个数为 2 的子数组，然后左边界1和上一个奇数（没有）之间的偶数个数为2 ，所以左边界右边界1和下一个奇数（也没有）之间的偶数个数为3，则 i=3 一共能贡献 (2+1) × (3+1) = 12 个奇数个数为2的子数组。

例2
[2,2,1,1,2,2,1,1,2,2] k = 2
i=2 开始的子数组 1,1 能贡献 3 × 3 = 9 个奇数个数为2的子数组
i=3 开始的子数组 1,2,2,1 能贡献 1 × 1 个奇数个数为2的子数组，因为其左右边界都紧邻着奇数，无法扩展
i=6 开始的子数组 1,2 能贡献 3 × 3 = 9 个奇数个数为2的子数组
所以最终结果为 9 + 1 + 9 = 19 个奇数个数为2的子数组

具体实现上，为了方便找 第 i 个奇数 和 第 i+k-1 个奇数以及其前后的偶数个数，我们先用一个数组 int[] odds 存储原数组中所有奇数的下标，则通过 odds[i] - odds[i-1] 就可以快速知道这两个奇数之间有多少个偶数。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    public int numberOfSubarrays(int[] nums, int k) {
        if (null == nums || nums.length < k) {
            return 0;
        }
        // 原数组中所有奇数的下标
        int[] odds = new int[nums.length];
        int oddsCount = 0;
        for(int i = 0, j = 0; i < nums.length; i++) {
            if ((nums[i] & 1) == 1) {
                odds[oddsCount++] = i;
            }
        }
        int res = 0;
        for (int i = 0; i <= oddsCount - k; i++) {
            // 左边界有多少种扩展，也就是左边界和上一个奇数之间的偶数个数+1
            int leftCount = i-1 >= 0 ? odds[i] - odds[i-1] : odds[i] + 1;
            // 右边界有多少种扩展，也就是右边界和下一个奇数之间的偶数个数+1
            int rightCount = i+k < oddsCount ? odds[i+k] - odds[i+k-1] : nums.length - odds[i+k-1];
            // 左边界扩展个数 * 右边界扩展个数，也就是第i个奇数开头的奇数个数为k的子数组能贡献的个数
            res += leftCount * rightCount;
        }
        return res;
    }
}

O(n^2)暴力方法

时间复杂度 O(n^2)，超时，23 / 38 个通过测试用例

// 暴力，超时，23 / 38 个通过测试用例
private static class SolutionV2020Brutal {
    public int numberOfSubarrays(int[] nums, int k) {
        if (null == nums || nums.length < k) {
            return 0;
        }
        int res = 0;

        for (int i = 0; i <= nums.length - k; i++) {
            // 统计以 nums[i] 开头的连续子数组的奇数个数
            int oddCount = 0;
            for (int j = i; j < nums.length; j++) {
                if ((nums[j] & 1) == 1) {
                    oddCount++;
                }
                if (oddCount == k) {
                    res++;
                } else if (oddCount > k) {
                    break;
                }
            }
        }
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_1248_CountNumberOfNiceSubarrays.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1248_CountNumberOfNiceSubarrays.java

---