1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target LeetCode Solution
In this guide, you will get 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Non-Overlapping Subarrays With Sum Equals Target problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
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.
1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target LeetCode Solution in C++
class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
// Ending the subarray ASAP always has a better result.
int ans = 0;
int prefix = 0;
unordered_set<int> prefixes{0};
// Greedily find the subarrays that equal to the target.
for (const int num : nums) {
// Check if there is a subarray ends in here and equals to the target.
prefix += num;
if (prefixes.contains(prefix - target)) {
// Find one and discard all the prefixes that have been used.
++ans;
prefix = 0;
prefixes = {0};
} else {
prefixes.insert(prefix);
}
}
return ans;
}
}; /* code provided by PROGIEZ */
1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target LeetCode Solution in Java
class Solution {
public static int maxNonOverlapping(int[] nums, int target) {
// Ending the subarray ASAP always has a better result.
int ans = 0;
int prefix = 0;
Set<Integer> prefixes = new HashSet<>(Arrays.asList(0));
// Greedily find the subarrays that equal to the target.
for (int num : nums) {
prefix += num;
// Check if there is a subarray ends in here and equals to the target.
if (prefixes.contains(prefix - target)) {
// Find one and discard all the prefixes that have been used.
ans++;
prefix = 0;
prefixes = new HashSet<>(Arrays.asList(0));
} else {
prefixes.add(prefix);
}
}
return ans;
}
} // code provided by PROGIEZ
1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target LeetCode Solution in Python
class Solution:
def maxNonOverlapping(self, nums: list[int], target: int) -> int:
# Ending the subarray ASAP always has a better result.
ans = 0
prefix = 0
prefixes = {0}
# Greedily find the subarrays that equal to the target.
for num in nums:
# Check if there is a subarray ends in here and equals to the target.
prefix += num
if prefix - target in prefixes:
# Find one and discard all the prefixes that have been used.
ans += 1
prefix = 0
prefixes = {0}
else:
prefixes.add(prefix)
return ans # code by PROGIEZ
