930. Binary Subarrays With Sum

class Solution:
    def numSubarraysWithSum(self, A: List[int], goal: int) -> int:
        """ tc O(N) sc O(1) (assuming each item in A is non-negtive )
        1. corner case if target < 0
        2. left, right ptr start with head. start with K, keep substract current item the right ptr pointing at
        3. keep reduce target K untill K < 0, start moving left ptr until K >=0
        4. each time we find a valid window [l,r], we add its length into res so we get the amount of subarrays within this subArray  
        
        """
        def atMost(K): # number of subarray at most goal
            if K < 0:
                return 0
            res = l = 0
            for r in range(len(A)):
                K -= A[r]
                while K < 0:
                    S += A[l]
                    l += 1
                res += r-l + 1
            return res 
        return atMost(goal) - atMost(goal-1)

class Solution:
    def numSubarraysWithSum(self, A: List[int], goal: int) -> int:
        """ tc O(N) sc O(N)
        main idea:  count occurance of each psum, when psum - goal is seen before, update res with d[psum-goal]
                    it also apply to negtive 
                    note, we need to add corner case psum == goal +1  so d[0] = 1

        there are two cases: 
        (1)  psum[:j] == goal
        (2)  psum[i:j] == goal => psum[i:j] = psum[:j] - psum[:i-1] = goal   ============>   psum[:j] -goal = psum[:i-1]
            ====> we are looking for is there any `psum[:j] -goal` exist before, which will be # of (i,j) pairs
        """
        psum = res = 0
        d = defaultdict(int) #Counter({0:1})
        d[0] = 1 # this is importanc!!!!!!!!
        for a in A:
            psum += a
            #if psum >= goal:
            res += d[psum-goal]
            d[psum] += 1
            
        return res