Maximum Number of Non-Overlapping Subarrays With Sum Equals Target LeetCode solution in Python

1
"""
2
greedy, prefix sum with hashtable
3
O(n), O(n)
4
"""
5

6

7
class Solution:
8
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
9
        # hash set to record previously encountered prefix sums
10
        prefix_sums = {0}
11

12
        res = prefix_sum = 0
13
        for num in nums:
14
            prefix_sum += num
15
            if prefix_sum - target in prefix_sums:
16
                res += 1
17
                # greedily discard prefix sums before num
18
                # thus not considering subarrays that start at before num
19
                prefix_sums = {prefix_sum}
20
            else:
21
                prefix_sums.add(prefix_sum)
22
        return res