leetcode 5471 和为目标值的最大数目不重叠非空子数组

5471. 和为目标值的最大数目不重叠非空子数组数目

给你一个数组 nums 和一个整数 target 。
请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。

示例 1：
输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。

关键点：子数组 (即连续的一个区间)
思路： 前缀和 + 贪心

如果能在找到满足 sum - target 的值，那么便找到一个子数组。并且为了防止重叠，前面的和全部不能再用了，直接把set清空。
（这里利用的是贪心的思想，找到一个算一个）

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int ans = 0;
        int sumB = 0;
        // 记录之前的前缀和 <前缀和,下标>
        unordered_set<int> s;
        s.insert(0);
        for(int i = 0; i < nums.size(); i++){
            sumB += nums[i];
            //之前的前缀和恰好有一个匹配
            if(s.find(sumB - target) != s.end()){
               ++ans;
               // 那么之前的前缀和都丢弃
               s.clear();
               // s.insert(0);
               sumB = 0;
            }
            s.insert(sumB);
        }
        return ans;
    }
};