Problem Statement in English

You’re given a binary array nums and an integer goal. You have to find the number of non-empty subarrays that have a sum equal to goal.

Return the number of such subarrays.

Approach

This is similar to problems like 560. Subarray Sum Equals K, 974. Subarray Sums Divisible By K and 3381. Maximum Subarray Sum With Length Divisible By K.

We simply maintain a hashmap to store the cumulative sums and their frequencies.

We iterate through the array, calculating the cumulative sum at each step. For each cumulative sum, we check if there is a previous cumulative sum that, when subtracted from the current cumulative sum, equals goal.

If such a cumulative sum exists in the hashmap, it means there are subarrays that sum up to goal, and we add their frequency to our result.

And we’re done!

Solution in Python


class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        hm = defaultdict(int)
        res = curr = 0
        hm[0] = 1

        for i in range(len(nums)):
            curr += nums[i]
            diff = curr - goal
            res += hm[diff]

            hm[curr] += 1

        return res

Complexity

  • Time: $O(n)$
    Since we’re iterating through the array once.

  • Space: $O(n)$
    Since we’re storing the cumulative sums in a hashmap.

And we are done.