Problem URL: Maximum number of non overlapping subarrays with sum equals target

We can be greedy and use a hash set to store the prefix sum. If the prefix sum minus target is in the hash set, then we will update the result and clear the hash set. We will return the result.

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        seen = set([0])
        res, cur = 0, 0
        for i, num in enumerate(nums):
            cur += num
            prev = cur - target
            if prev in seen:
                res += 1
                seen = set()
            seen.add(cur)

        return res

Time complexity: O(n)
Space complexity: O(n)