和为目标值且不重叠的非空子数组的最大数目Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个数组 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
# 思路
对每一段总和都用set保存下来，判断之前是否有某段+target=当前段
# 解法
class Solution {
public int maxNonOverlapping(int[] nums, int target) {
Set<Integer> set = new HashSet<>();
int curSum = 0;
int res = 0;
set.add(0);
for (int num : nums) {
curSum += num;
if (set.contains(curSum - target)) {
// 如果当前段和减去之前某一段和为target，则符合条件，即当前curSum=上次curSum+target
set.clear();
set.add(0);
curSum = 0;
res++;
} else {
// 还未满足条件，保留当前段的和
set.add(curSum);
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 总结
- 分析出几种情况，然后分别对各个情况实现
