力扣1546. 和为目标值且不重叠的非空子数组的最大数目

根据数据范围和题意可知，应该用前缀和+哈希，这一题和之前写的一道十分类似也可以说是之前那一道题的弱化版，是我在写1477那道题最初的思路：

力扣1477. 找两个和为目标值且不重叠的子数组

本题不用像lc1477那样整一个dp表，而是直接用一个变量保存上一个子数组的末尾last，再用新枚举到的子数组的开始位置与last比较，判断它们是不是重叠即可，如果不重叠就ans++，实际上这是一种贪心的思想

class Solution {
public:int sum[100005];
unordered_map<int,int> mp;int maxNonOverlapping(vector<int>& nums, int target) {for(int i=0;i<nums.size();i++){sum[i+1]=sum[i]+nums[i];}mp[0]=0;int last=-1;int ans=0;//sum[j+1]-sum[i]=targetfor(int j=0;j<nums.size();j++){if(mp.count(sum[j+1]-target)){int start=mp[sum[j+1]-target]+1;if(start>last){ans++;last=j+1;}}mp[sum[j+1]]=j+1;}return ans;}
};

时间复杂度O(n).