Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Binary Subarrays With Sum (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class Solution:

    def numSubarraysWithSum(self, nums, goal):
        count = 0
        j = 0

        add = 0

        for i in range(len(nums)):
            
            add += nums[i]

            # move j only if add becomes larger than goal 0
            while add > goal:
                add -= nums[j]
                j += 1

            if add == goal:
                count += 1 # without prefix 0

                # j wont move but we want to count all the prefix 0 . 
                # like 0 0 1 1 goal 2 answer = 3
                k = j 
                while nums[k] == 0:
                    count += 1
                    k += 1

        return count
A

Anonymous

· 2 years ago

In Example 1: Wrong: "Justification: The subarrays with a sum of 3"

Right: "Justification: The subarrays with a sum of 2"

Reading Progress

0%

Vote for new content