README.md

1546. 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.

Constraints:

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

Solutions (Rust)

1. Solution

use std::collections::HashMap;

impl Solution {
    pub fn max_non_overlapping(nums: Vec<i32>, target: i32) -> i32 {
        let mut prefix_sum = vec![0; nums.len() + 1];
        let mut last_index = HashMap::from([(0, 0)]);
        let mut max_count = vec![0; nums.len() + 1];

        for i in 0..nums.len() {
            prefix_sum[i + 1] = prefix_sum[i] + nums[i];
            if let Some(&j) = last_index.get(&(prefix_sum[i + 1] - target)) {
                max_count[i + 1] = max_count[j] + 1;
            }
            max_count[i + 1] = max_count[i + 1].max(max_count[i]);
            last_index.insert(prefix_sum[i + 1], i + 1);
        }

        *max_count.last().unwrap()
    }
}