README.md

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

English Version

题目描述

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

解法

贪心 + 前缀和。ans 表示结果，初始值为 0。

贪心：当我们发现以下标 i 结尾的子数组和为 target 时，ans++，然后继续往后查找。

Python3

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        i, n = 0, len(nums)
        ans = 0
        while i < n:
            s = 0
            seen = {0}
            while i < n:
                s += nums[i]
                if s - target in seen:
                    ans += 1
                    break
                i += 1
                seen.add(s)
            i += 1
        return ans

Java

class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int i = 0, n = nums.length;
        int ans = 0;
        while (i < n) {
            int s = 0;
            Set<Integer> seen = new HashSet<>();
            seen.add(0);
            while (i < n) {
                s += nums[i];
                if (seen.contains(s - target)) {
                    ++ans;
                    break;
                }
                ++i;
                seen.add(s);
            }
            ++i;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int i = 0, n = nums.size();
        int ans = 0;
        while (i < n) {
            int s = 0;
            unordered_set<int> seen;
            seen.insert(0);
            while (i < n) {
                s += nums[i];
                if (seen.count(s - target)) {
                    ++ans;
                    break;
                }
                ++i;
                seen.insert(s);
            }
            ++i;
        }
        return ans;
    }
};

Go

func maxNonOverlapping(nums []int, target int) int {
	i, n, ans := 0, len(nums), 0
	for i < n {
		s := 0
		seen := map[int]bool{0: true}
		for i < n {
			s += nums[i]
			if seen[s-target] {
				ans++
				break
			}
			seen[s] = true
			i++
		}
		i++
	}
	return ans
}

...