Subarray sum equals k

Array Hash Table Prefix Sum

46.8% acceptance

Jan 13, 2026

24830

842

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
    use std::collections::HashMap;
    let mut count = 0;
    let mut prefix_sum = 0;
    let mut map: HashMap<i32, i32> = HashMap::new();
    map.insert(0, 1);
    for &num in &nums {
      prefix_sum += num;
      count += map.get(&(prefix_sum - k)).copied().unwrap_or(0);
      *map.entry(prefix_sum).or_insert(0) += 1;
    }
    count
  }
}