## 325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

```Input: nums = `[1, -1, 5, -2, 3]`, k = `3`
Output: 4
Explanation: The subarray `[1, -1, 5, -2]` sums to 3 and is the longest.
```

Example 2:

```Input: nums = `[-2, -1, 2, 1]`, k = `1`
Output: 2
Explanation: The subarray `[-1, 2]` sums to 1 and is the longest.```

Can you do it in O(n) time?

## Rust Solution

``````struct Solution;
use std::collections::HashMap;

impl Solution {
fn max_sub_array_len(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut prefix = vec![0; n];
let mut prev = 0;
let mut hm: HashMap<i32, Vec<usize>> = HashMap::new();
hm.entry(0).or_default().push(0);
for i in 0..n {
prefix[i] = nums[i] + prev;
prev = prefix[i];
hm.entry(prev).or_default().push(i + 1);
}
let mut res = 0;
for i in 0..n {
if let Some(v) = hm.get(&(prefix[i] - k)) {
for &j in v {
if i + 1 > j {
res = res.max(i + 1 - j);
}
}
}
}
res as i32
}
}

#[test]
fn test() {
let nums = vec![1, -1, 5, -2, 3];
let k = 3;
let res = 4;
assert_eq!(Solution::max_sub_array_len(nums, k), res);
let nums = vec![-2, -1, 2, 1];
let k = 1;
let res = 2;
assert_eq!(Solution::max_sub_array_len(nums, k), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.