[Leetcode] 1248. Count Number of Nice Subarrays

https://leetcode.com/problems/count-number-of-nice-subarrays/description/

initial

my initial thought is if we can find valid starting points where this subarray's odd number freq. is exactly k, then we can add by that amount of starting points. But I actually thought that while (odd_so_far==k), we can just do ans+=1 while shifting left pointer to right. But this isnt true.

Lets say we have
[2,2,2,1,2,2,1,2,2,2]
The first valid subarray is [2,2,2,1,2,2,1]. We have valid start point of [2,2,2,1] for this subarray so we add +4 to tmp count variable. Now lets see [2,2,2,1,2,2,1,2]. This subarray is also valid so we should not just increemnt ans by 1 but with the previous tmp count variable cuz we can do
[2,2,2,1,2,2,1,2][,2,2,1,2,2,1,2]
[,,2,1,2,2,1,2][,,,1,2,2,1,2]

Think of it as like extending the previous result.

Only when we meet a odd number do we set the tmp count variable as 0 cuz we need a new starting point cuz now we have 1 more odd number than required.

sol

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n= len(nums)
        left=ans=0
        acc=0
        tmp=0
        for right in range(len(nums)):
            if nums[right]%2==1:
                acc+=1
                tmp=0
            while acc==k:
                if nums[left]%2==1:
                    acc-=1
                tmp+=1
                left+=1
            ans+=tmp
        return ans

another off. sol

Actually this q is using maths theory.
Exactly K times = at most K times - at most K - 1 times

At most K:      {0, 1, 2, 3, ..., K-1, K}
At most (K-1):  {0, 1, 2, 3, ..., K-1}
Difference:     {K}  <-- This is "Exactly K"

    def numberOfSubarrays(self, A, k):
        def atMost(k):
            res = i = 0
            for j in xrange(len(A)):
                k -= A[j] % 2
                while k < 0:
                    k += A[i] % 2
                    i += 1
                res += j - i + 1
            return res

        return atMost(k) - atMost(k - 1)

complexity

n time
1 space