# 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
###### tags: `Leetcode` `Medium` `Greedy` `Prefix Sum`
Link: https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
## 思路 $O(N)$ $O(N)$

## Code

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int[] prefixSum = new int[nums.length+1];
        for(int i = 0;i < nums.length;i++){
            prefixSum[i+1] = prefixSum[i]+nums[i];
        }
        int ans = 0;
        int prev = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < prefixSum.length;i++){
            int remain = prefixSum[i]-target;
            if(map.containsKey(remain) && map.get(remain)>=prev){
                ans+=1;
                prev=i;
            }
            map.put(prefixSum[i],i);
        }
        return ans;
    }
}