1248、统计【优美子数组】
给你一个整数数组 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）
链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 题解
## 1、双指针+缓存+数据简化
- 通过指针可以很好的处理特殊子序列的问题。
- 缓存、数据简化可以有效避免重复计算。
```java
class Solution {
int[] memo;
public int numberOfSubarrays(int[] nums, int k) {
int count = 0;
for (int i = 0;i < nums.length;i++) {
// 奇数置为1 偶数置为0
nums[i] = nums[i] & 1;
count += nums[i];
}
if (count < k){
return 0;
}
int start = 0,end = 0,res = 0;
memo = new int[nums.length];
count = 0;
while(end < nums.length){
if (nums[end] != 0) {
count++;
}
if (count < k){
// System.out.println("case1:count < k");
end++;
} else if(count > k){
// System.out.println("case2:count > k");
while(start < nums.length && nums[start] == 0){
start++;
}
start++;
// System.out.println("start: "+start);
// print(nums,start,end);
res += countSub(nums,start);
count--;
end++;
} else {
// System.out.println("case3:count = k");
// print(nums,start,end);
res += countSub(nums,start);
end++;
}
}
return res;
}
private int countSub(int[] nums,int start){
if (memo[start] > 0) {
return memo[start];
}
int len = 0;
int i = 0;
while(start+i < nums.length && nums[start + i] == 0){
i++;
len++;
}
len++;
// System.out.println("len: " + len);
memo[start] = len;
return len;
}
private void print(int[] nums,int start,int end){
System.out.print("sub: [");
for (int i = start;i <= end;i++){
System.out.print(nums[i]);
if (i != end){
System.out.print(",");
}
}
System.out.println("]");
}
}
2、数学计算
建立奇数的索引数组。对于第 i 个奇数，它对答案的贡献为符合条件的 [l,r] 的个数，即：
（i之前的偶数个数+1）* （（i+k-1）之后的偶数个数）：
$$(\textit{odd}[i] - \textit{odd}[i - 1]) * (\textit{odd}[i + k] - \textit{odd}[i + k - 1])$$
C++实现
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = (int)nums.size();
// 建立索引数组
int odd[n + 2], ans = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] & 1) odd[++cnt] = i;
}
// 边界值处理
odd[0] = -1, odd[++cnt] = n;
// 对于每个奇数进行计算贡献
for (int i = 1; i + k <= cnt; ++i) {
ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
}
return ans;
}
};
> 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/tong-ji-you-mei-zi-shu-zu-by-leetcode-solution/
Java实现
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int n = nums.length;
// 建立索引数组
int odd[n + 2], ans = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] & 1) odd[++cnt] = i;
}
// 边界值处理
odd[0] = -1, odd[++cnt] = n;
// 对于每个奇数进行计算贡献
for (int i = 1; i + k <= cnt; ++i) {
ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1]);
}
return ans;
}
}
3、前缀和 + 差分
处理原来的数组，将所有的偶数置位后面最近一个奇数的累加值。
例如：
[2,2,2,1,2,2,1,2,2,2] ->
[1,2,3,1,2,3,1,2,3,4]
这样计算
c++实现
class Solution {
vector<int> cnt;
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = (int)nums.size();
cnt.resize(n + 1, 0);
int odd = 0, ans = 0;
cnt[0] = 1;
for (int i = 0; i < n; ++i) {
odd += nums[i] & 1;
ans += odd >= k ? cnt[odd - k] : 0;
cnt[odd] += 1;
}
return ans;
}
};
> 链接：https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/tong-ji-you-mei-zi-shu-zu-by-leetcode-solution/
java实现
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int n = nums.length;
int[] cnt = new int[n+1];
int odd = 0, ans = 0, cnt = 0;
cnt[0] = 1;
for (int i = 0;i < n;i++) {
// 当前奇数的索引标
odd += nums[i] & 1;
// 奇数个数达到目标值
ans += odd >= k ? cnt[odd - k] : 0;
// 更新前缀和数组
cnt[odd] += 1;
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
