1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target Medium

1/**
2 * [1546] Maximum Number of Non-Overlapping Subarrays With Sum Equals Target
3 *
4 * 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.
5 *  
6 * Example 1:
7 *
8 * Input: nums = [1,1,1,1,1], target = 2
9 * Output: 2
10 * Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).
11 *
12 * Example 2:
13 *
14 * Input: nums = [-1,3,5,1,4,2,-9], target = 6
15 * Output: 2
16 * Explanation: There are 3 subarrays with sum equal to 6.
17 * ([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.
18 *
19 *  
20 * Constraints:
21 *
22 * 1 <= nums.length <= 10^5
23 * -10^4 <= nums[i] <= 10^4
24 * 0 <= target <= 10^6
25 *
26 */
27pub struct Solution {}
28
29// problem: https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/
30// discuss: https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/discuss/?currentPage=1&orderBy=most_votes&query=
31
32// submission codes start here
33use std::collections::HashSet;
34impl Solution {
35    pub fn max_non_overlapping(nums: Vec<i32>, target: i32) -> i32 {
36        let mut result = 0;
37        let mut prefix_sum = 0;
38        let mut set = HashSet::new();
39        set.insert(0);
40
41        for n in nums {
42            prefix_sum += n;
43            if set.contains(&(prefix_sum - target)) {
44                result += 1;
45                prefix_sum = 0;
46                set.clear();
47                set.insert(0);
48            } else {
49                set.insert(prefix_sum);
50            }
51        }
52        result
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_1546() {
64        assert_eq!(Solution::max_non_overlapping(vec![1, 1, 1, 1, 1], 2), 2);
65    }
66}
67