-
Notifications
You must be signed in to change notification settings - Fork 0
/
1248. count number of nice subarrays
62 lines (58 loc) · 1.23 KB
/
1248. count number of nice subarrays
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
#brute time complexity ->0(n**2) space 0(n)
// int numberOfSubarrays(vector<int>& nums, int k) {
// long long s=0;
// for(int i=0;i<nums.size();i++)
// {
// long long ki=0;
// for(int j=i;j<nums.size();j++)
// {
// if(nums[j]%2!=0)
// {
// ki++;
// }
// if(ki==k)
// {
// s++;
// }
// if(ki>k) break;
// }
// }
// return (int)s;
// }
//tc o(n) sc 0(1)
int pi(vector<int> &nums,int k)
{
if(k<0) return 0;
int m=0;
int l=0;
int r=0;
int s=0;
while(r<nums.size())
{
if(nums[r]%2!=0)
{
s++;
}
while(s>k){
if(nums[l]%2!=0){
s--;
}
l++;
}
if(s<=k)
{
m+=r-l+1;
}
r++;
}
return m;
}
int numberOfSubarrays(vector<int>& nums, int k) {
int goal=pi(nums,k);
int goal1=pi(nums,k-1);
int ans=goal-goal1;
return ans;
}
};