题目描述

给你一个数组 nums 和一个整数 target。

请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target。

样例

输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1]，它们的和为目标值 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 个是不重叠的。

输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3

输入：nums = [0,0,0], target = 0
输出：3

限制

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

算法

(动态规划，哈希表) $O(n)$

1. 设状态 $f(i)$ 表示前 $i$ 个数字组成非空不重叠子数组的最大数目，$i$ 的有效下标从 1 开始。
2. 初始时，$f(0) = 0$，其余待定。
3. 转移时，如果不选择 $nums(i)$，则转移 $f(i) = f(i - 1)$，如果选择 $nums(i)$，需要找到以 $nums(i)$ 为结尾时最大的 $last$，满足区间 [last + 1, i] 的和为 target，如果存在这样的 $last$，则转移 $f(i) = \max(f(i), f(last) + 1)$。
4. 最终答案为 $f(n)$。
5. 寻找最大 $last$ 时可以使用哈希表 $seen$，哈希表中存储每种前缀和对应的最大下标。初始时，$seen(0) = 0$。

时间复杂度

• 状态数为 $O(n)$，转移时间为常数，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储状态和哈希表。

Go 代码

func maxNonOverlapping(nums []int, target int) int {
    var sum int
    seen := make(map[int]int)

    n := len(nums)
    f := make([]int, n + 1)
    seen[0] = 0

    for i := 1; i <= n; i++ {
        sum += nums[i - 1]
        f[i] = f[i - 1]

        if last, ok := seen[sum - target]; ok {
            if f[i] < f[last] + 1 {
                f[i] = f[last] + 1
            }
        }

        seen[sum] = i
    }

    return f[n]
}