---

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

• 标签：贪心、数组、哈希表、前缀和
• 难度：中等

题目链接

• 1546. 和为目标值且不重叠的非空子数组的最大数目 - 力扣

题目大意

描述：给定一个数组 $nums$ 和一个整数 $target$。

要求：返回可以找到的互不重叠的非空子数组的最大数目，每个子数组的和都等于 $target$。

说明：

• $1 \le nums.length \le 10^5$。
• $-10^4 \le nums[i] \le 10^4$。
• $-10^6 \le target \le 10^6$。

示例：

• 示例 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 个是不重叠的。

解题思路

思路 1：贪心 + 前缀和 + 哈希表

1. 核心思想

为了得到最大数量的不重叠子数组，应该每次找到和等于 $target$ 的子数组后，立即选择它（贪心），然后继续向后找。因为在当前最早结束的位置选择一个子数组，能为后面的子数组留出最多空间。

具体地，使用哈希表记录前缀和的最新位置。遍历数组，维护当前前缀和 $cur$。如果 $cur - target$ 在哈希表中，说明存在一个和为 $target$ 的子数组。选择它，然后重置哈希表（仅保留 $0$ 位置），继续向后。

2. 贪心正确性证明

这是一个区间调度问题。每个和为 $target$ 的子数组可以看作一个区间。要最大化不重叠区间的数量，按右端点最早进行贪心选择是最优的。

我们维护 $seen$ 集合（记录当前轮次的前缀和），一旦找到 $cur - target \in seen$，说明找到了以当前位置为右端点的最短满足条件的子数组。立即选择它，然后清空 $seen$ 重新开始，等价于选择了右端点最早的区间。

3. 具体步骤

第 1 步：$cur = 0$，$ans = 0$。
第 2 步：$seen = set()$，$seen.add(0)$。
第 3 步：遍历每个 $x$：

• $cur += x$。
• 如果 $cur - target \in seen$：$ans += 1$，清空 $seen$，$seen.add(0)$，$cur = 0$。
• 否则：$seen.add(cur)$。

4. 举例说明

以 $nums = [1,1,1,1,1], target = 2$ 为例：

• $i=0$：$cur=1$，$seen=\{0,1\}$，$cur-target=-1\notin seen$。
• $i=1$：$cur=2$，$cur-target=0\in seen$，$ans=1$，重置 $seen=\{0\}$，$cur=0$。
• $i=2$：$cur=1$，$seen=\{0,1\}$。
• $i=3$：$cur=2$，$cur-target=0\in seen$，$ans=2$，重置。
• $i=4$：$cur=1$，$seen=\{0,1\}$。

最终 $ans=2$。

以 $nums = [-1,3,5,1,4,2,-9], target = 4$ 为例：

• 子数组 $[-1,3,5,1,4,2,-9]$ 和为 $5$，不是 $4$。
• $i=0$：$cur=-1$，$seen=\{0,-1\}$。
• $i=1$：$cur=2$，$cur-target=-2\notin seen$。
• $i=2$：$cur=7$，$cur-target=3\notin seen$。
• $i=3$：$cur=8$，$cur-target=4\notin seen$。
• $i=4$：$cur=12$，$cur-target=8\in seen$（$8$ 是 $i=3$ 时的前缀和），说明 $[4,4]$ 和为 $4$，$ans=1$，重置。

最终 $ans=1$。

思路 1：代码

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        seen = set()
        seen.add(0)
        cur = 0
        ans = 0

        for x in nums:
            cur += x
            if cur - target in seen:
                ans += 1
                seen = set()
                seen.add(0)
                cur = 0
            else:
                seen.add(cur)

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，一次遍历。
• 空间复杂度：$O(n)$，哈希表。