Medium

题目描述

给你一个数组 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 个是不重叠的。

提示：

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

解题思路

这道题要求找到和为目标值且不重叠的非空子数组的最大数目。核心思路是贪心算法 + 前缀和。

解题思路：

  1. 贪心策略：一旦找到一个和为 target 的子数组，立即将其加入结果中。这样做是最优的，因为延迟选择不会带来更好的结果。

  2. 前缀和 + 哈希集合：

    • 使用前缀和来快速计算子数组的和
    • 对于当前位置的前缀和 prefixSum，如果存在之前的前缀和 prefixSum - target，说明存在一个和为 target 的子数组
    • 使用哈希集合存储已见过的前缀和

  3. 算法流程：

    • 遍历数组，维护当前前缀和
    • 检查 prefixSum - target 是否在集合中存在
    • 如果存在，说明找到了一个目标子数组，计数器加1，清空集合重新开始
    • 将当前前缀和加入集合

  4. 为什么要清空集合：因为找到一个子数组后，为了保证不重叠，需要从下一个位置重新开始计算前缀和。

这个贪心策略是正确的，因为任何延迟选择子数组的方案都不会比立即选择更优。

代码实现

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int count = 0;
        unordered_set<int> seen;
        int prefixSum = 0;
        seen.insert(0);
        
        for (int num : nums) {
            prefixSum += num;
            if (seen.count(prefixSum - target)) {
                count++;
                seen.clear();
                seen.insert(0);
                prefixSum = 0;
            } else {
                seen.insert(prefixSum);
            }
        }
        
        return count;
    }
};

class Solution:
    def maxNonOverlapping(self, nums: List[int], target: int) -> int:
        count = 0
        seen = {0}
        prefix_sum = 0
        
        for num in nums:
            prefix_sum += num
            if prefix_sum - target in seen:
                count += 1
                seen = {0}
                prefix_sum = 0
            else:
                seen.add(prefix_sum)
        
        return count

public class Solution {
    public int MaxNonOverlapping(int[] nums, int target) {
        int count = 0;
        HashSet<int> seen = new HashSet<int> {0};
        int prefixSum = 0;
        
        foreach (int num in nums) {
            prefixSum += num;
            if (seen.Contains(prefixSum - target)) {
                count++;
                seen.Clear();
                seen.Add(0);
                prefixSum = 0;
            } else {
                seen.Add(prefixSum);
            }
        }
        
        return count;
    }
}

var maxNonOverlapping = function(nums, target) {
    let count = 0;
    let seen = new Set([0]);
    let prefixSum = 0;
    
    for (let num of nums) {
        prefixSum += num;
        if (seen.has(prefixSum - target)) {
            count++;
            seen = new Set([0]);
            prefixSum = 0;
        } else {
            seen.add(prefixSum);
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，哈希集合操作为 O(1)
空间复杂度O(n)最坏情况下哈希集合存储所有前缀和