用双指针扫描奇数为k个的区间。确定区间[j, i]后用指针j2在区间[j, i]内统计奇数为k个的区间
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size(), ans = 0, cnt = 0;
for (int i = 0, j = 0; i<n; i++){
cnt += nums[i] % 2;
while (cnt > k)
cnt -= nums[j++] % 2;
if (cnt == k){
int j2 = j, cnt2 = cnt;
while (cnt2 == k){
ans++;
cnt2 -= nums[j2++] % 2;
}
}
}
return ans;
}
};
另外一个思路是参照大佬wzc1995 lc992的 代码
const int N = 50010;
class Solution {
public:
int lower[N], upper[N];
int n;
void solve(vector<int>& nums, int arr[], int k){
int cnt = 0;
for (int i = 0, j = 0; i<n; i++){
cnt += nums[i] % 2;
while (cnt > k)
cnt -= nums[j++] % 2;
if (cnt == k)
arr[i] = j;
}
}
int numberOfSubarrays(vector<int>& nums, int k) {
n = nums.size();
memset(lower, 0, sizeof lower);
memset(upper, 0, sizeof upper);
solve(nums, lower, k);
solve(nums, upper, k-1);
int ans = 0;
for (int i = 0; i<n; i++)
ans += upper[i] - lower[i];
return ans;
}
};