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

https://leetcode-cn.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/

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

通过次数2,993 | 提交次数8,105

First Try

2020-08-17

重点在于对前缀和概念的理解和使用，然后叠加贪心算法才能高低复杂度搞定。

周赛的时候用了动态规划，考虑前面所有子序列加上当前元素的和是否等于target，然后重新开始计算子序列，测试案例都正确，但结果是O(N^2)算法，一直超时。

前缀和:

对于数组nums，构建preSum对应数组，在preSum index的位置，放置的是nums[0...index]的所有数字之和。

如果想要知道数组任意位置i,j之间连续数组的和，则使用preSum[j] - preSum[i]即可快速得到，从一个O(N^2)算法变成O(N)算法，构建完缓存后还可以认为是O(1)算法。这就是前缀和的核心技巧。

对应该题，需要寻找的是preSum[j] - preSum[i] = target, 因此只要preSum[j] - target在当前前缀数组里，说明存在i使用连续数组i-j之和等于target. 为了保证数组之间不重复交错，直接清理前缀数组，从下一个元素继续算起，重新开始计算前缀和。

golang solution

func maxNonOverlapping(nums []int, target int) int {
    // 前缀和
    preSum := make(map[int]bool)
    preSum[0] = true  // 自身也不能遗忘
    currSum := 0 
    count := 0 
    for _, n := range(nums) {
        currSum += n 
        if _, ok := preSum[currSum - target]; ok {
            count += 1
            preSum = make(map[int]bool)
            preSum[0] = true 
            currSum = 0 
        }
        preSum[currSum] = true 
    }
    return count 
}

执行用时：136 ms, 在所有 Go 提交中击败了87.72%的用户
内存消耗：8.5 MB, 在所有 Go 提交中击败了85.96%的用户

python solution

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        pre_sum = set([0])
        curr_sum = 0
        rv = 0 
        for n in nums:
            curr_sum += n 
            if curr_sum - target in pre_sum:
                rv += 1
                pre_sum = set([0])
                curr_sum = 0 
            else:
                pre_sum.add(curr_sum)
        return rv 

执行用时：152 ms, 在所有 Python3 提交中击败了77.49%的用户
内存消耗：20.5 MB, 在所有 Python3 提交中击败了62.62%的用户

Time Exceeded Try

2020-08-10

动态规划+贪婪算法写法，每次考虑前面所有连续子序列加上这个元素后是否能凑成target，如果凑成，则放弃前面的所有序列，从新元素再次考虑这个过程。

问题在于每次考虑前面所有连续子序列的和，对于每个元素都要遍历前面的n个元素，相当于O(N^2)算法，于是就超时了。超时的数组测试有8万个元素，都是非常小的数字，target却是十几万，导致前面无数次无效计算，刚好就是O(N^2)算法。

改为前缀和序列算法，就可以解决这个问题。思路一遍，速度飞起。

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        # 先用backtrack找出所有数组？ 然后再用贪心算法找出最多的不重叠数组？
        # 或者可以一起完成？
        # 连续数组，而不是任意元素
        
        print(len(nums), sum(nums))
        return 
        
        maxv = {"c": 0}
        def backtrack(sidx, eidx, seq, nums):
            # print(maxv, sidx, eidx, seq)
            if eidx > len(nums) - 1:
                return
            if nums[eidx] == target:
                maxv["c"] += 1
                backtrack(eidx, eidx + 1, [], nums)
                return 
            flag = False 
            nseq = [nums[eidx]]
            for val in seq:
                nseq.append(nums[eidx] + val)
                if nseq[-1] == target:
                    maxv["c"] += 1
                    backtrack(eidx, eidx + 1, [], nums)
                    flag = True 
                    break  # 避免 0的出现导致多重允许
            if not flag:
                backtrack(sidx, eidx + 1, nseq, nums)
        
        backtrack(0, 0, [], nums)
        return maxv["c"]
    