Prefix Sum + HashSet() main question :
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
seen = {0}
size = len(nums)
cnt = 0
preSum = 0
for num in nums:
preSum += num
if preSum - target in seen:
cnt += 1
seen = {0}
preSum = 0
seen.add(preSum)
return cnt
Solution 2 Greedy ==> if add one more j to transist, OJ will TLE
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
i = 0
size = len(nums)
res = 0
while i <size :
seen = {0}
_sum = 0
while i < size :
_sum += nums[i]
if _sum - target in seen:
res += 1
break
else:
seen.add(_sum)
i += 1
i += 1
return res