How do I find the maximum number of non-overlapping subarrays with a given sum?

You can solve this problem using array scanning and prefix sum techniques. By using a hash map to track prefix sums, you can efficiently check for subarrays that sum to the target and prevent overlap.

What is the time complexity of the optimal solution?

The optimal solution runs in O(n) time, as it only requires a single pass through the array and hash lookups for each element.

What are some common mistakes when solving this problem?

Common mistakes include not resetting the sum after finding a valid subarray, using inefficient brute-force solutions, and incorrectly handling negative numbers or non-zero targets.

Can the algorithm handle negative numbers in the array?

Yes, the algorithm works with negative numbers as well. It still relies on prefix sums, and hash lookup ensures correct identification of subarrays.

What does the greedy approach refer to in this problem?

The greedy approach refers to selecting subarrays as soon as their sum equals the target and then resetting the sum to prevent overlap. This maximizes the number of non-overlapping subarrays.

#1546

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

和为目标值且不重叠的非空子数组的最大数目

给你一个数组 nums 和一个整数 target 。请你返回非空不重叠子数组的最大数目，且每个子数组中数字和都为 target 。示例 1：输入： nums = [1,1,1,1,1], target = 2 输出： 2 解释：总共有 2 个不重叠子数组（加粗数字表示） [ 1,1 ,1…

数组哈希表贪心前缀和

题目描述

给你一个数组 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

lightbulb

解题思路

方法一：贪心 + 前缀和 + 哈希表

我们遍历数组 $nums$ ，利用前缀和 + 哈希表的方法，寻找和为 $target$ 的子数组，若找到，则答案加一，然后我们将前缀和置为 $0$ ，继续遍历数组 $nums$ ，直到遍历完整个数组。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate knowledge of prefix sum techniques.
question_mark
The candidate should explain how to handle overlap prevention efficiently.
question_mark
The candidate should show awareness of optimizing both time and space complexity.

warning

常见陷阱

外企场景

error
Forgetting to reset the sum after finding a valid subarray, leading to overlaps.
error
Using a brute-force approach with nested loops instead of efficient scanning.
error
Incorrectly handling negative numbers or non-zero target sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array contains negative numbers? Can the approach still work?
arrow_right_alt
How would you adapt the solution if there were multiple possible target sums?
arrow_right_alt
What if the sum of the subarray needs to be greater than or less than the target?

help

常见问题

外企场景

继续练习

#1488 避免洪水泛滥 #1481 不同整数的最少数目 #1442 形成两个异或相等数组的三元组数目