代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个数组 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
我们遍历数组 $nums$,利用前缀和 + 哈希表的方法,寻找和为 $target$ 的子数组,若找到,则答案加一,然后我们将前缀和置为 $0$,继续遍历数组 $nums$,直到遍历完整个数组。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
ans = 0
i, n = 0, len(nums)
while i < n:
s = 0
vis = {0}
while i < n:
s += nums[i]
if s - target in vis:
ans += 1
break
i += 1
vis.add(s)
i += 1
return ans
class Solution {
public int maxNonOverlapping(int[] nums, int target) {
int ans = 0, n = nums.length;
for (int i = 0; i < n; ++i) {
Set<Integer> vis = new HashSet<>();
int s = 0;
vis.add(0);
while (i < n) {
s += nums[i];
if (vis.contains(s - target)) {
++ans;
break;
}
++i;
vis.add(s);
}
}
return ans;
}
}
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int ans = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
unordered_set<int> vis{{0}};
int s = 0;
while (i < n) {
s += nums[i];
if (vis.count(s - target)) {
++ans;
break;
}
++i;
vis.insert(s);
}
}
return ans;
}
};
func maxNonOverlapping(nums []int, target int) (ans int) {
n := len(nums)
for i := 0; i < n; i++ {
s := 0
vis := map[int]bool{0: true}
for ; i < n; i++ {
s += nums[i]
if vis[s-target] {
ans++
break
}
vis[s] = true
}
}
return
}
function maxNonOverlapping(nums: number[], target: number): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
let s = 0;
const vis: Set<number> = new Set();
vis.add(0);
for (; i < n; ++i) {
s += nums[i];
if (vis.has(s - target)) {
++ans;
break;
}
vis.add(s);
}
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。