难度: Medium
给你一个数组 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^40 <= target <= 10^6运行时间: 76 ms
内存: 23.7 MB
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
s=0
a=0
j=set()
j.add(0)
for i in nums:
s+=i
if s-target in j:
a+=1
s=0
j.clear()
j.add(s)
return a
该题解采用前缀和与哈希表的组合策略来寻找和为目标值的子数组，并确保子数组是不重叠的。首先初始化一个前缀和变量s和计数器a。同时使用一个集合j来记录遇到的前缀和以及初始值0（代表从数组开头到当前位置的子数组）。遍历数组nums中的每个元素，将元素值累加到s。对于每一个新的s值，检查s-target是否已存在于集合j中。如果存在，说明找到了一个和为target的子数组，此时a加1表示找到一个符合条件的子数组，并重置s和清空集合j以避免重叠。每次迭代也将新的s加入集合j。最终，a的值即为所求的最大不重叠子数组数目。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
s = 0 # 初始化前缀和
a = 0 # 初始化计数器，用于记录符合条件的子数组数量
j = set() # 初始化集合，用于存储前缀和
j.add(0) # 添加初始前缀和0，表示可以从数组开头开始计算
for i in nums: # 遍历数组元素
s += i # 更新前缀和
if s - target in j: # 检查是否存在一个前缀和，使得当前前缀和减去它等于目标值
a += 1 # 找到一个符合条件的子数组
s = 0 # 重置前缀和，避免重叠
j.clear() # 清空集合，避免重叠
j.add(s) # 将当前前缀和添加到集合
return a # 返回符合条件的子数组数量
在找到一个符合条件的子数组后，重置前缀和s和清空集合j的目的是为了确保后续找到的子数组不与之前的子数组重叠。通过重置s和清空j，算法可以从当前找到的子数组的下一个元素重新开始计算新的子数组，这样可以保证每个找到的子数组都是独立的，满足题目要求的不重叠条件。
使用集合j来存储前缀和在数据量大时可能会面临性能问题。尽管集合提供了较快的查找时间复杂度（通常为O(1)），但如果数据量非常大，存储大量的前缀和会占用大量内存。此外，每次找到符合条件的子数组后清空集合，再重新添加新的前缀和也会带来额外的计算和存储开销。因此，在极大数据量的情况下，这种方法可能不是最效率的选择。
算法通过在每次找到符合条件的子数组后重置前缀和s并清空集合j来确保子数组不重叠。这种方法意味着一旦找到一个符合条件的子数组，算法会停止考虑当前子数组中的任何元素，并从下一个元素开始新的子数组寻找过程。这就确保了所有找到的子数组均是独立的，从而避免了子数组之间的重叠。
将前缀和s重置为0的主要优势是简化了不重叠子数组的管理，使算法可以从清晰的初始状态开始寻找下一个子数组。这降低了错误累积的风险并清晰地界定了每个子数组的边界。劣势是可能会错过一些潜在的子数组组合，因为重置s意味着放弃了从当前子数组中间开始的任何可能的子数组。然而，考虑到题目要求子数组不重叠，这种做法是合理的，因为它确保了子数组之间的独立性。