[1248] Count Number of Nice Subarrays

經過了前面幾題滑窗戶的荼毒之後，想當然耳這題也是用atMost 的滑窗戶解決

但是Hint 有提示，可以把奇數設成1，偶數設成0，然後再用prefix sum ???!!!

於是自己亂揣之後，弄出一個也不知道是不是正確的解法= =+

大意就是含k個奇數的範圍裡，去相乘它們的個數，再加總。

而零到一要特別處理，給它加一個 1 這樣。 （為什麼啊？！哈XD！)

為了算個數的方便，還對prefix sum 弄了一個count array，也就是說，假使input 是

[2,2,2,1,2,2,1,2,2,2] （或任何更醜的數字）

先把它變成0, 1 array

[0,0,0,1,0,0,1,0,0,0]

然後算一個prefix sum 出來

[0,0,0,1,1,1,2,2,2,2]

再去做一個count array 

[3,3,4] 表是0有三個，1有三個，2有四個。

用目測法去看呢, k = 2的時候，表示含有兩個 1 的區間是 左邊有(3+1)個，右邊是4 個長度

所以答案是4*4。接著就左邊右邊一個一個相加，去加總k個奇數的時候會有幾種可能這樣。

（好廢，我連我自己都無法說服QQ)

程式碼在這裡QQ

int numberOfSubarrays(int* nums, int numsSize, int k){

for (int i=0; i< numsSize;i++)

{

if (nums[i]%2==0)

nums[i]=0;

else

nums[i]=1;

if (i>0)

nums[i]= nums[i-1]+nums[i];

}

int l=0;

int r=0;

int count =0;

int *countarray= calloc (nums[numsSize-1] +1, sizeof(int));

for (int i=0; i<numsSize; i++)

countarray[nums[i]]++;

if (countarray[0]==numsSize || nums[numsSize-1] < k)

return 0;

for (int r=k; r<=nums[numsSize-1]; r++)

{

if(l== 0)

count += countarray[r] * (countarray[l]+1);

else

count += countarray[r] * countarray[l];

l++;

}

return count;

}

至於，atMost 的解法在這兒

int atMostSum(int* nums, int numsSize, int goal)
{
    int l,r,sum,ret;
    l=0;
    r=0;
    sum=0;
    ret =0;
    while (r < numsSize)
    {   
        sum+=nums[r];
        while (l <=r && sum > goal)
        {
            sum-= nums[l];
            l++;
        }

        ret+=(r-l)+1;
        r++;
    }
    return ret;
}

int numberOfSubarrays(int* nums, int numsSize, int k){
    for (int i=0; i< numsSize;i++)
    {
        if (nums[i]%2==0)
            nums[i]=0;
        else
            nums[i]=1;
    }
    return atMostSum(nums, numsSize, k) -atMostSum(nums, numsSize, k-1);
}