Skip to main content

rustgym/leetcode/
_325_maximum_size_subarray_sum_equals_k.rs

1struct Solution;
2use std::collections::HashMap;
3
4impl Solution {
5    fn max_sub_array_len(nums: Vec<i32>, k: i32) -> i32 {
6        let n = nums.len();
7        let mut prefix = vec![0; n];
8        let mut prev = 0;
9        let mut hm: HashMap<i32, Vec<usize>> = HashMap::new();
10        hm.entry(0).or_default().push(0);
11        for i in 0..n {
12            prefix[i] = nums[i] + prev;
13            prev = prefix[i];
14            hm.entry(prev).or_default().push(i + 1);
15        }
16        let mut res = 0;
17        for i in 0..n {
18            if let Some(v) = hm.get(&(prefix[i] - k)) {
19                for &j in v {
20                    if i + 1 > j {
21                        res = res.max(i + 1 - j);
22                    }
23                }
24            }
25        }
26        res as i32
27    }
28}
29
30#[test]
31fn test() {
32    let nums = vec![1, -1, 5, -2, 3];
33    let k = 3;
34    let res = 4;
35    assert_eq!(Solution::max_sub_array_len(nums, k), res);
36    let nums = vec![-2, -1, 2, 1];
37    let k = 1;
38    let res = 2;
39    assert_eq!(Solution::max_sub_array_len(nums, k), res);
40}