LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target Solution in Java, C++, Python & More | Explanation + Code

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.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)