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 同步地址:
https://github.com/grandyang/leetcode/issues/1248
类似题目:
Number of Substrings Containing All Three Characters
Replace the Substring for Balanced String
Subarrays with K Different Integers
Shortest Subarray with Sum at Least K
参考资料:
https://leetcode.com/problems/count-number-of-nice-subarrays/
https://leetcode.com/problems/count-number-of-nice-subarrays/discuss/419483/Subarray-Sum-Equals-K
LeetCode All in One 题目讲解汇总(持续更新中...)