Question

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

解法

方法一：贪心 + 前缀和 + 哈希表

我们遍历数组 $nums$，利用前缀和 + 哈希表的方法，寻找和为 $target$ 的子数组，若找到，则答案加一，然后我们将前缀和置为 $0$，继续遍历数组 $nums$，直到遍历完整个数组。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

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

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

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

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

function maxNonOverlapping(nums: number[], target: number): number {
  const n = nums.length;
  let ans = 0;
  for (let i = 0; i < n; ++i) {
    let s = 0;
    const vis: Set<number> = new Set();
    vis.add(0);
    for (; i < n; ++i) {
      s += nums[i];
      if (vis.has(s - target)) {
        ++ans;
        break;
      }
      vis.add(s);
    }
  }
  return ans;
}