class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
}
};
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^40 <= target <= 10^6原站题解
golang 解法, 执行用时: 96 ms, 内存消耗: 9.7 MB, 提交时间: 2023-09-23 10:33:30
func maxNonOverlapping(nums []int, target int) int {
m := make(map[int]int, len(nums)+1) // 前缀和索引
m[0] = -1 // 默认0值索引
preSum := 0
res := 0
from := -1 // 记录起始位置，避免重复
for i := 0; i < len(nums); i++ {
preSum += nums[i] // 构造前缀和
// 存在前缀和差值为target, 且索引位置不重复
if idx, exist := m[preSum-target]; exist && idx >= from {
res++
from = i
}
// hash 记录
m[preSum] = i
}
return res
}
golang 解法, 执行用时: 164 ms, 内存消耗: 12.4 MB, 提交时间: 2023-09-23 10:33:13
func maxNonOverlapping(nums []int, target int) int {
ans := 0
sum := 0
mp := map[int]int{}
mp[0] = -1
reached := -1
for i,n:=range nums{
sum += n
if v,ok := mp[sum-target];ok{
if v>=reached{
ans ++
reached = i
}
}
mp[sum] = i
}
return ans
}
cpp 解法, 执行用时: 176 ms, 内存消耗: 80.8 MB, 提交时间: 2023-09-23 10:32:45
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size(), count = 0;
vector<int> prefix(n, 0);
prefix[0] = nums[0];
for(int i = 1; i < n; i++){
prefix[i] = prefix[i - 1] + nums[i];
}
unordered_map<int, int> myMap; //(前缀和,次数)
myMap[0] = 1; // prefix[-1] = 0
for(int i = 0; i < n; i++){
if(myMap.find(prefix[i] - target) != myMap.end()){
count++;
myMap.clear(); //保证不重叠
}
myMap[prefix[i]]++; // i = j - 1; j = i + 1,保证不重叠
}
return count;
}
};
python3 解法, 执行用时: 132 ms, 内存消耗: 24.2 MB, 提交时间: 2023-09-23 10:32:19
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
java 解法, 执行用时: 32 ms, 内存消耗: 54.3 MB, 提交时间: 2023-09-23 10:32:06
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;
}
}
cpp 解法, 执行用时: 204 ms, 内存消耗: 94.6 MB, 提交时间: 2023-09-23 10:31:52
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;
}
};