Question

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

中文文档

Description

Given an array nums and an integer target, return _the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to_ target.

 

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 0 <= target <= 106

Solutions

Solution 1: Greedy + Prefix Sum + Hash Table

We traverse the array $nums$, using the method of prefix sum + hash table, to find subarrays with a sum of $target$. If found, we increment the answer by one, then we set the prefix sum to $0$ and continue to traverse the array $nums$ until the entire array is traversed.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $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;
}