Given an array nums and an integer target, return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

&nbsp;
Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).


Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	-104 &lt;= nums[i] &lt;= 104
	0 &lt;= target &lt;= 106


'''
greedy, prefix sum with hashtable
O(n), O(n)
'''
class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        # hash set to record previously encountered prefix sums
        prefix_sums = {0}
        
        res = prefix_sum = 0
        for num in nums:
            prefix_sum += num
            if prefix_sum - target in prefix_sums:
                res += 1
                # greedily discard prefix sums before num
                # thus not considering subarrays that start at before num 
                prefix_sums = {prefix_sum} 
            else:
                prefix_sums.add(prefix_sum)
        return res
class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        Map<Integer, Integer> valToPos = new HashMap<>();
        int sums = 0;
        int count = 0;
        int lastEndPos = 0;
        valToPos.put(0, 0);
        for (int i = 0; i < nums.length; i++) {
            sums += nums[i];
            int pos = valToPos.getOrDefault(sums - target, -1);
            if (pos >= lastEndPos) {
                count += 1;
                lastEndPos = i + 1;
            }
            valToPos.put(sums, i + 1);
        }
        return count;
    }
}
class Solution {
public:
    unordered_map<int,int> mpp ;
    int maxNonOverlapping(vector<int>& nums, int target) {

        int sum = 0 , ways = 0 , prev = INT_MIN ;
        mpp[0] = -1 ;
        for(int i = 0 ; i < nums.size() ; ++i ){
            sum += nums[i] ;
            if(mpp.find(sum - target) != end(mpp) and mpp[sum-target] >= prev ) ++ways , prev = i ;
            mpp[sum] = i ;
        }
        return ways ;
    }
};
var maxNonOverlapping = function(nums, target) {
    const seen = new Set();
    let total = 0, result = 0;
    
    for(let n of nums) {
        total += n;
        
        if(total === target || seen.has(total - target)) {
            total = 0;
            result++;
            seen.clear()
        } else seen.add(total)
    }
    return result;
};
Maximum Number of Non-Overlapping Subarrays With Sum Equals Target