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

给你一个数组 nums 和一个整数 target 。

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

示例 1：

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

示例 2：

**输入：** nums = [-1,3,5,1,4,2,-9], target = 6
**输出：** 2
**解释：** 总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。

示例 3：

**输入：** nums = [-2,6,6,3,5,4,1,2,8], target = 10
**输出：** 3

示例 4：

**输入：** nums = [0,0,0], target = 0
**输出：** 3

提示：

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

方法一：贪心

思路与算法

由于题目要求所有的子数组互不重叠，因此对于某个满足条件的子数组，如果其右端点是所有满足条件的子数组的右端点中最小的那一个，则该子数组一定会被选择。

故可以使用贪心算法：从左到右遍历数组，一旦发现有某个以当前下标 i 为右端点的子数组和为 target，就给计数器的值加 1，并从数组 nums 的下标 i+1 开始，进行下一次寻找。

为了判断是否存在和为 target 的子数组，我们在遍历的过程中记录数组的前缀和，并将它们保存在哈希表中。如果位置 i 对应的前缀和为 sum}_i，而 sum}_i-\textit{target 已经存在于哈希表中，就说明找到了一个和为 target 的子数组。

如果找到了一个符合条件的子数组，则接下来遍历时需要用一个新的哈希表，而不是使用原有的哈希表，因为要确保每次找到的子数组都与此前找到的不重合。

代码

[sol1-C++]

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int size = nums.size();
        int ret = 0;
        int i = 0;
        while (i < size) {
            unordered_set <int> s = {0};
            int sum = 0;
            while (i < size) {
                sum += nums[i];
                if (s.find(sum - target) != s.end()) {
                    ret++;
                    break;
                } else {
                    s.insert(sum);
                    i++;
                }
            }
            i++;
        }
        return ret;
    }
};

[sol1-Java]

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int size = nums.length;
        int ret = 0;
        int i = 0;
        while (i < size) {
            Set<Integer> set = new HashSet<Integer>() { {
                add(0);
            } };
            int sum = 0;
            while (i < size) {
                sum += nums[i];
                if (set.contains(sum - target)) {
                    ret++;
                    break;
                } else {
                    set.add(sum);
                    i++;
                }
            }
            i++;
        }
        return ret;
    }
}

[sol1-Python3]

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        size = len(nums)
        ret = 0
        i = 0
        while i < size:
            s = {0}
            total = 0
            while i < size:
                total += nums[i]
                if total - target in s:
                    ret += 1
                    break
                else:
                    s.add(total)
                    i += 1
            i += 1
        return ret

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组 nums 的长度。我们要遍历数组的每个元素，其中哈希表的插入和查询都只需要单次 O(1) 的时间。

• 空间复杂度：O(N)，因为哈希表中最多保存 O(N) 个元素。