[LeetCode] 1248. Count Number of Nice Subarrays #1248

grandyang · 2019-05-30T16:33:42Z

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

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

这道题给了一个数组 nums，和一个正整数k，定义了一种 nice 子数组，即子数组中有k个奇数，现在问有多少个 nice 子数组。由于求的是子数组，所以必须是连续的，而如果把每个子数组当作一个窗口的话，就不难想到可以用滑动窗口 Sliding Window 来做，LeetCode 中使用滑动窗口的题目还挺多的，可以参见末尾列出的类似题目。在不遍历所有子数组的情况下，求正好有K个奇数并不是很容易，这道题需要稍稍转换一下思维，比较好求的求最多有K个奇数的情况。若能分别求出最多有K个奇数的子数组的个数，和最多有 K-1 个奇数的子数组的个数，二者相减，就是正好有K个奇数的子数组的个数。

我们之前做过这样一道题目 Subarrays with K Different Integers，这里采用几乎完全一样的思路。由于要同时求K和 K-1 的情况，所以可以用个子函数来做。在 atMost 函数中，定义窗口左边界的位置 left，初始化为0。然后开始遍历，对于每个遍历到的数字，若是奇数，则k自减1。由于窗口内不能有超过k个的奇数，所以当k小于0时，要进行循环，缩小窗口，即右移左边界，当移除一个奇数的时候，k就自增1。此时窗口的大小就代表了此时最多有k个奇数的子数组的个数，将其加入结果 res，这样直至 for 循环退出后，就可以得到最终的结果了，参见代码如下：

解法一：

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }
    int atMost(vector<int>& nums, int k) {
        int res = 0, left = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            k -= nums[i] % 2;
            while (k < 0) {
                k += nums[left++] % 2;
            }
            res += i - left + 1;
        }
        return res;
    }
};

再来看一种解法，这种思路的核心是统计偶数的个数，只需要一次遍历即可完成。还是要借用滑动窗口的方法，维护一个刚好有k个奇数的窗口，当首次将k个奇数放到窗口中时，当前窗口可能不是最短的，需要统计左起连续0的个数。比如数组数组是 [0, 0, 1, 0, 1, 0, 0]，k=2 时，则首次找到的窗口是 [0, 0, 1, 0, 1]，显然不是最短的，这里最短的窗口为 [1, 0, 1]，需要统计左起0的个数，有两个0，再加上最短的那个窗口，目前为止总共有三个子数组符合题意，加到结果 res 中。然后继续右移右边界，若还是遇到了偶数，则之前所有的情况再加上这个偶数，就又是一个新的子数组，所以可以直接把 cnt 再加到结果 res 中，直到遇到奇数，cnt 清零，开始一轮同样的处理，参见代码如下：

解法二：

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int res = 0, left = 0, cnt = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] % 2 == 1) {
                --k;
                cnt = 0;
            }
            while (k == 0) {
                k += nums[left++] & 1;
                ++cnt;
            }
            res += cnt;
        }
        return res;
    }
};

这道题如果把奇数都当作1，偶数都当作0，那么含有k个奇数的子数组其实就是和为k的子数组，就变成之前那道 Subarray Sum Equals K 了，用一个 HashMap 来建立子数组之和跟其出现次数之间的映射，初始化要加入 {0,1} 这对映射，这是为啥呢，因为解题思路是遍历数组中的数字，用 cur 来记录到当前位置的累加和，建立 HashMap 的目的是为了可以快速的查找 cur-k 是否存在，即是否有连续子数组的和为 cur-k，如果存在的话，那么和为k的子数组一定也存在，这样当 cur 刚好为k的时候，那么数组从起始到当前位置的这段子数组的和就是k，满足题意，如果 HashMap 中事先没有 m[0] 项的话，这个符合题意的结果就无法累加到结果 res 中，这就是初始化的用途。上面讲解的内容顺带着也把 for 循环中的内容解释了，这里就不多阐述了，有疑问的童鞋请在评论区留言哈，参见代码如下：

解法三：

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int res = 0, cur = 0, n = nums.size();
        unordered_map<int, int> m{{0, 1}};
        for (int i = 0; i < n; ++i) {
            cur += nums[i] & 1;
            res += m[cur - k];
            ++m[cur];
        }
        return res;
    }
};

Github 同步地址:

#1248

类似题目：

Number of Substrings Containing All Three Characters

Replace the Substring for Balanced String

Max Consecutive Ones III

Binary Subarrays With Sum

Subarrays with K Different Integers

Fruit Into Baskets

Shortest Subarray with Sum at Least K

Minimum Size Subarray Sum

Subarray Sum Equals K