给你一个整数数组 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 <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
解法1 数学
这个题目中偶数其实是没有用的，可以单独建立一个 o d d odd odd 数组来记录第 i i i 个奇数的下标。那么枚举奇数，假设当前枚举到第 i i i 个，那么 [ o d d [ i ] , o d d [ i + k − 1 ] ] [odd[i],odd[i+k−1]] [odd[i],odd[i+k−1]] 这个子数组就恰好包含 k k k 个奇数。由于奇数和奇数间存在偶数，所以一定存在其他子数组 [ l , r ] [l,r] [l,r] 、满足 [ l , r ] [l,r] [l,r] 包含 [ o d d [ i ] , o d d [ i + k − 1 ] ] [odd[i],odd[i+k−1]] [odd[i],odd[i+k−1]] 且 [ l , r ] [l,r] [l,r] 里的奇数个数为 k k k 个，那么这个需要怎么统计呢？
由于已经记录了每个奇数的下标，所以知道对于第 i i i 个奇数，它的前一个奇数的下标为 o d d [ i − 1 ] odd[i−1] odd[i−1] ，也就是说 ( o d d [ i − 1 ] , o d d [ i ] ) (odd[i−1],odd[i]) (odd[i−1],odd[i]) 间的数都为偶数。同理可得 ( o d d [ i + k − 1 ] , o d d [ i + k ] ) (odd[i+k−1],odd[i+k]) (odd[i+k−1],odd[i+k]) 间的数也都为偶数。那么可以得出——满足 l ∈ ( o d d [ i − 1 ] , o d d [ i ] ] l∈(odd[i−1],odd[i]\ ] l∈(odd[i−1],odd[i] ] 且 r ∈ [ o d d [ i + k − 1 ] , o d d [ i + k ] ) r∈[odd[i+k−1],odd[i+k]) r∈[odd[i+k−1],odd[i+k]) 条件的子数组 [ l , r ] [l,r] [l,r] ，包含 [ o d d [ i ] , o d d [ i + k − 1 ] ] [odd[i],odd[i+k−1]] [odd[i],odd[i+k−1]] 且 [ l , r ] [l,r] [l,r] 里的奇数个数为 k k k 个。因此对于第 i i i 个奇数，它对答案的贡献为符合条件的 [ l , r ] [l,r] [l,r] 的个数，即：
( o d d [ i ] − o d d [ i − 1 ] ) × ( o d d [ i + k ] − o d d [ i + k − 1 ] ) (odd[i]−odd[i−1])×(odd[i+k]−odd[i+k−1]) (odd[i]−odd[i−1])×(odd[i+k]−odd[i+k−1])
只要遍历一遍 o d d odd odd 数组即可求得最后的答案，注意边界的处理。
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
int odd[n + 2], cnt = 0;
for (int i = 0; i < n; ++i)
if (nums[i] & 1) odd[++cnt] = i; // 记录第cnt个奇数的下标
odd[0] = -1, odd[++cnt] = n; // 两个哨兵
for (int i = 1; i + k <= cnt; ++i) // cnt已经加了1
ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
return ans;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)，其中 n n n 为数组的大小。遍历 o d d odd odd 数组最坏情况下需要 O ( n ) O(n) O(n) 的时间。
- 空间复杂度： O ( n ) O(n) O(n)，其中 n n n 为数组的大小。 o d d odd odd 数组需要 O ( n ) O(n) O(n) 的空间。
解法2 前缀和+哈希表
考虑以 i i i 结尾的「优美子数组」个数，我们需要统计符合条件的下标 j j j 的个数，其中 0 ≤ j ≤ i 0≤j≤i 0≤j≤i 这个子数组里的奇数个数恰好为 k k k 。如果枚举 [ 0.. i ] [0..i] [0..i] 里所有的下标来判断是否符合条件，那么复杂度将会达到 O ( n 2 ) O(n^2) O(n2) ，无法通过所有测试用例，因此需要优化枚举的时间复杂度。
我们定义 s u m [ i + 1 ] sum[i+1] sum[i+1] 为 [ 0.. i ] [0..i] [0..i] 中奇数的个数，则 s u m [ i + 1 ] sum[i+1] sum[i+1] 可以由 s u m [ i ] sum[i] sum[i] 和 n u m s [ i ] nums[i] nums[i] 递推而来，即：
s u m [ i + 1 ] = s u m [ i ] + ( n u m s [ i ] & 1 ) sum[i+1]=sum[i]+(nums[i]\& 1) sum[i+1]=sum[i]+(nums[i]&1)
那么「 [ j . . . i ] [j...i] [j...i] 这个子数组里的奇数个数恰好为 k k k 」这个条件可转化为
s u m [ i + 1 ] − s u m [ j ] = = k sum[i+1]−sum[j]==k sum[i+1]−sum[j]==k
简单移项，可得符合条件的下标 j j j 需要满足
s u m [ j ] = = s u m [ i + 1 ] − k sum[j]==sum[i+1]−k sum[j]==sum[i+1]−k
所以，考虑以 i i i 结尾的「优美子数组」个数时，只要统计有多少个奇数个数为 s u m [ i + 1 ] − k sum[i+1]−k sum[i+1]−k 即可。我们只要建立频次数组/哈希表 c n t cnt cnt 记录 s u m [ i ] sum[i] sum[i] 出现的次数，从左往右边更新 c n t cnt cnt 边计算答案，那么以 i i i 结尾的答案 c n t [ s u m [ i ] − k ] cnt[sum[i]−k] cnt[sum[i]−k] 即可 O ( 1 ) O(1) O(1) 得到。最后的答案即为所有下标结尾的「优美子数组」个数之和。
需要注意的是，从左往右边更新边计算时，已经保证了 c n t [ s u m [ i + 1 ] − k ] cnt[sum[i+1]−k] cnt[sum[i+1]−k] 里记录的 s u m [ j ] sum[j] sum[j] 的下标范围是 0 ≤ j ≤ i 0≤j≤i 0≤j≤i 。同时，由于 s u m [ i ] sum[i] sum[i] 的计算只与前一项的答案有关，因此可以不用建立 s u m sum sum 数组，直接用 s u m sum sum 变量来记录即可。
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size(), sum = 0, ans = 0;
// unordered_map<int, int> cnt;
int cnt[n + 1];
memset(cnt, 0, sizeof(cnt));
cnt[0] = 1;
for (int i = 0; i < n; ++i) {
sum += (nums[i] & 1);
ans += sum >= k ? cnt[sum - k] : 0;
++cnt[sum];
}
return ans;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)，其中 n n n 为数组的大小。只需遍历一遍数组即可求得答案。
- 空间复杂度： O ( n ) O(n) O(n)，其中 n n n 为数组的大小。频次数组 c n t cnt cnt 记录的最大值不会超过 n n n ，因此只需要额外的 O ( n ) O(n) O(n) 的空间。
解法3 快慢指针+滑动窗口
这个解法是解法1的空间优化版。我们不断右移 r i g h t right right 指针来扩大滑动窗口，使其包含 k k k 个奇数；若当前滑动窗口包含了 k k k 个奇数，则如下「计算当前窗口的优美子数组个数」：
- 统计第 1 1 1 个奇数左边的偶数个数 l e f t E v e n C n t leftEvenCnt leftEvenCnt 。 这 l e f t E v e n C n t leftEvenCnt leftEvenCnt 个偶数都可以作为「优美子数组」的起点，因此起点的选择有 l e f t E v e n C n t + 1 leftEvenCnt + 1 leftEvenCnt+1 种（因为可以一个偶数都不取）。
- 统计第 k k k 个奇数右边的偶数个数 r i g h t E v e n C n t rightEvenCnt rightEvenCnt 。 这 r i g h t E v e n C n t rightEvenCnt rightEvenCnt 个偶数都可以作为「优美子数组」的终点，因此终点的选择有 r i g h t E v e n C n t + 1 rightEvenCnt + 1 rightEvenCnt+1 种（因为可以一个偶数都不取）。
- 因此「优美子数组」左右起点的选择组合数为 ( l e f t E v e n C n t + 1 ) × ( r i g h t E v e n C n t + 1 ) (leftEvenCnt + 1) \times (rightEvenCnt + 1) (leftEvenCnt+1)×(rightEvenCnt+1) 。
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
int left = 0, right = 0, oddCnt = 0;
while (right < n) {
// 右指针先走,每遇到一个奇数则+1
if (nums[right++] & 1) ++oddCnt;
// 若当前滑动窗口[left,right)有k个奇数,进入此分支统计当前滑动窗口中优美子数组个数
if (oddCnt == k) {
// 先将滑动窗口右边界向右拓展,直到遇到下个奇数(或出界)
// rightEvenCnt即为第k个奇数右边的偶数个数
int tmp = right;
while (right < n && (nums[right] & 1) == 0) ++right;
int rightEvenCnt = right - tmp;
// leftEventCnt即为第1个奇数左边的偶数个数
int leftEventCnt = 0;
while ((nums[left] & 1) == 0) {
++leftEventCnt;
++left;
}
// 第1个奇数左边的leftEvenCnt个偶数都可作为优美子数组的起点
// 因为第1个奇数左边可1个偶数都不取,所以起点的选择有leftEvenCnt + 1 种）
// 第k个奇数右边的rightEvenCnt个偶数都可作为优美子数组的终点
// 因为第k个奇数右边可以1个偶数都不取,所以终点的选择有 rightEvenCnt + 1 种）
// 所以该滑动窗口中,优美子数组左右起点的选择组合数为(leftEvenCnt + 1)*(rightEvenCnt + 1)
ans += (leftEventCnt + 1) * (rightEvenCnt + 1);
// 此时left指向的是第1个奇数,因为该区间已经统计完了,因此left右移一位,oddCnt--
++left;
--oddCnt;
}
}
return ans;
}
};
复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)