题目

https://leetcode.com/contest/weekly-contest-201/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
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.

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.
Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3
Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

思路

记录累计和，同时每次只需要找 s[i] – target 的位置，然后max(dp+1,dp)，即分别对应是否选择第 i 位，其中寻找 s[i]-target 时，从后向前找，第一个命中即可，因为dp[i+1]>=dp[i],即数组越长，则值一定越大，所以贪心保证选择i后的子序列最短即可。
为了提高效率，使用map记录，其中为了避免保证找到的索引一定小于i，在更新dp后再更新map

源码

class Solution {
public:
    vector<int> dp,s;
    map<int,int> m;
    int maxNonOverlapping(vector<int>& nums, int target) {
        dp.resize(nums.size()+1,0);
        s.resize(nums.size()+1,0);
        int sum = 0;

        for(int i = 0;i<nums.size();++i){
            sum+=nums[i];
            s[i]=sum;

            dp[i] = dp[i==0?0:i-1];
            if(nums[i]==target){ 
                dp[i]++;
                cout<<"a "<<i<<" "<<dp[i]<<endl;
                m[sum] = i;
                continue;
            }
            if(m.count(s[i]-target)!=0){
                dp[i]=max(dp[i],dp[m[s[i]-target]]+1);
                cout<<"b "<<i<<" "<<dp[i]<<endl;
            }else if(s[i]==target){
                dp[i]=max(dp[i],1);
                cout<<"c "<<i<<" "<<dp[i]<<endl;
            }
             m[sum] = i;

        }
        return dp[nums.size()-1];
    }
};