Maximum size subarray sum equals k

Array Hash Table Prefix Sum

50.8% acceptance

Mar 31, 2026

2127

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sub_array_len(nums: Vec<i32>, k: i32) -> i32 {
    use std::collections::HashMap;
    let mut map: HashMap<i64, usize> = HashMap::new();
    map.insert(0, 0);
    let mut prefix = 0i64;
    let k = k as i64;
    let mut max_len = 0i32;
    for (i, &num) in nums.iter().enumerate() {
      prefix += num as i64;
      if let Some(&idx) = map.get(&(prefix - k)) {
        max_len = max_len.max((i + 1 - idx) as i32);
      }
      map.entry(prefix).or_insert(i + 1);
    }
    max_len
  }
}