Skip to main content
Back to problems
#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)
LeetCode
solution.rs
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
  }
}