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

mid

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

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

1
2
3
4
5
示例 1：

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

1
2
3
4
5
6
示例 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 个是不重叠的。

贪心 + 前缀和

贪心：由于题目要求所有的子数组互不重叠，因此对于某个满足条件的子数组，如果其右端点是所有满足条件的子数组的右端点中最小的那一个，则该子数组一定会被选择。

前缀和见 560 题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 贪心 + 前缀和
func maxNonOverlapping(nums []int, target int) int {
   count, curSum := 0, 0
   hash := map[int]int{0: 1}
   for i := 0; i < len(nums); i++ {
      curSum += nums[i]
      if hash[curSum-target] > 0 {
         count++ // 只记录一个
         // 清空前缀和记录
         hash = map[int]int{}
         curSum = 0
      }
      hash[curSum]++
   }
   return count
}