Count number of nice subarrays

Array Hash Table Math Sliding Window Prefix Sum

74.8% acceptance

Feb 25, 2026

5375

144

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_subarrays(nums: Vec<i32>, k: i32) -> i32 {
    // prefix[i] = number of odd numbers in nums[0..i]
    // We want count of (i, j) pairs where prefix[j] - prefix[i] == k
    let mut prefix_count = std::collections::HashMap::new();
    prefix_count.insert(0, 1);
    let mut odd_count = 0;
    let mut ans = 0;

    for x in nums {
      if x % 2 != 0 { odd_count += 1; }
      ans += prefix_count.get(&(odd_count - k)).copied().unwrap_or(0);
      *prefix_count.entry(odd_count).or_insert(0) += 1;
    }
    ans
  }
}