给你一个数组 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
提示 1
Keep track of prefix sums to quickly look up what subarray that sums "target" can be formed at each step of scanning the input array.
提示 2
It can be proved that greedily forming valid subarrays as soon as one is found is optimal.
解法:前缀和 + 哈希集 + 贪心
由于题目要求所有的子数组互不重叠,因此对于某个满足条件的子数组,如果其右端点是所有满足条件的子数组的右端点中最小的那一个,则该子数组一定会被选择。
故可以使用贪心算法:从左到右遍历数组,一旦发现有某个以当前下标 i 为右端点的子数组和为 target,就给计数器的值加 1,并从数组 nums 的下标 i+1 开始,进行下一次寻找。
为了判断是否存在和为 target 的子数组,我们在遍历的过程中记录数组的前缀和,并将它们保存在哈希表中。如果位置 i 对应的前缀和为 sumi,而 sumi−target 已经存在于哈希表中,就说明找到了一个和为 target 的子数组。
如果找到了一个符合条件的子数组,则接下来遍历时需要用一个新的哈希表,而不是使用原有的哈希表,因为要确保每次找到的子数组都与此前找到的不重合。
Java版:
class Solution {
public int maxNonOverlapping(int[] nums, int target) {
int ans = 0;
int presum = 0;
Set<Integer> set = new HashSet<>();
set.add(0);
for (int i = 0; i < nums.length; i++) {
presum += nums[i];
if (set.contains(presum - target)) {
ans++;
presum = 0;
set.clear();
set.add(0);
} else {
set.add(presum);
}
}
return ans;
}
}
Python3版:
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
ans = 0
presum = 0
pre = set()
pre.add(0)
for num in nums:
presum += num
if presum - target in pre:
ans += 1
pre.clear()
pre.add(0)
presum = 0
else:
pre.add(presum)
return ans
复杂度分析
- 时间复杂度:O(N),其中 N 为数组 nums 的长度。我们要遍历数组的每个元素,其中哈希表的插入和查询都只需要单次 O(1) 的时间。
- 空间复杂度:O(N),因为哈希表中最多保存 O(N) 个元素。