【LeetCode】统计「优美子数组」Java 题解

2021 年 12 月 13 日
本文字数：1265 字
阅读完需：约 4 分钟

题目描述

给你一个整数数组 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法每日一题是统计优美子数组，题目给出了定义如果某个连续子数组中恰好有 k 个奇数数字。因此，我们只需要关注奇数即可。如何区分数字的奇偶性呢？我们只需要 num % 2 取余，偶数的余数是 0，奇数的余数是 1。
题目要求返回请返回这个数组中「优美子数组」的数目。因此，我们只需要关注数目，不需要枚举每一个优美子数组。上一步，我们将 nums 转换为基偶数，降低了计算的复杂度。这里可以用前缀和的思想来统计，因为偶数的余数是 0，奇数的余数是 1。所以前缀和，统计的就是奇数出现的次数。
上面的思路大家都是清晰的，有同学对 cnt[] 这种缓存方式有疑问? 这里的 cnt[] 就是当缓存使用，我们常用的缓存是 map。cnt[] 一般是存储数字类的缓存，占用空间小，效率高。而 map 这种，缓存的 key 可以是数字，也可以是字符串，更加灵活一些。
对于 cnt 这种用法，我们可以参考一个简单的题目，有效的字母异位词, 来帮助你理解。

class Solution {    public boolean isAnagram(String s, String t) {        if (s.length() != t.length()) {            return false;        }        int[] cnt = new int[26];        for (int i = 0; i < s.length(); i++) {            cnt[s.charAt(i) - 'a']++;        }        for (int i = 0; i < t.length(); i++) {            cnt[t.charAt(i) - 'a']--;            if (cnt[t.charAt(i) - 'a'] < 0) {                return false;            }        }        return true;    }}

复制代码

在有效的字母异位词题目中，cnt 用来统计字符出现的次数。提升算法执行效率。

通过代码

class Solution {    public int numberOfSubarrays(int[] nums, int k) {        int n = nums.length;        int[] S = new int[n + 1];        S[0] = 0;        for (int i = 1; i <= n; i++) {            S[i] = S[i - 1] + nums[i - 1] % 2;        }
        int ans = 0;                int[] cnt = new int[n + 1];        cnt[S[0]]++;        for (int i = 1; i <= n; i++) {            if (S[i] - k >= 0) {                ans += cnt[S[i] - k];            }            cnt[S[i]]++;        }
        return ans;    }}