Subarrays with k different integers

Array Hash Table Sliding Window Counting

67.6% acceptance

Feb 25, 2026

6903

119

Given an integer array nums and an integer k, return the number of good subarrays of nums. A good array is an array where the number of different integers in that array is exactly k. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. A subarray is a contiguous part of an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn subarrays_with_k_distinct(nums: Vec<i32>, k: i32) -> i32 {
    fn at_most(nums: &Vec<i32>, k: i32) -> i32 {
      let mut count = std::collections::HashMap::new();
      let (mut l, mut res) = (0i32, 0i32);
      for r in 0..nums.len() as i32 {
        *count.entry(nums[r as usize]).or_insert(0) += 1;
        while count.len() > k as usize {
          let v = count.get_mut(&nums[l as usize]).unwrap();
          *v -= 1;
          if *v == 0 { count.remove(&nums[l as usize]); }
          l += 1;
        }
        res += r - l + 1;
      }
      res
    }
    at_most(&nums, k) - at_most(&nums, k - 1)
  }
}