#1546
Medium Algorithms Maximum number of non overlapping subarrays with sum equals target
Array Hash Table Greedy Prefix Sum
48.8% acceptance
Feb 25, 2026
1113
28
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.
Solution
Rust
Time O(n)
Space O(n)
impl Solution {
pub fn max_non_overlapping(nums: Vec<i32>, target: i32) -> i32 {
let mut count = 0;
let mut prefix = 0i64;
let mut seen = std::collections::HashSet::new();
seen.insert(0i64);
for x in nums {
prefix += x as i64;
if seen.contains(&(prefix - target as i64)) {
count += 1;
seen.clear();
seen.insert(prefix);
} else {
seen.insert(prefix);
}
}
count
}
}