Binary subarrays with sum

Array Hash Table Sliding Window Prefix Sum

68.3% acceptance

Feb 25, 2026

4797

167

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal. A subarray is a contiguous part of the array.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_subarrays_with_sum(nums: Vec<i32>, goal: i32) -> i32 {
    let mut count = std::collections::HashMap::new();
    count.insert(0i32, 1i32);
    let mut prefix = 0i32;
    let mut ans = 0i32;
    for &x in &nums {
      prefix += x;
      ans += count.get(&(prefix - goal)).copied().unwrap_or(0);
      *count.entry(prefix).or_insert(0) += 1;
    }
    ans
  }
}