Maximum sum of distinct subarrays with length k

Array Hash Table Sliding Window

42.8% acceptance

Feb 25, 2026

2298

You are given an integer array nums and an integer k. Find the maximum subarr ay sum of all the subarrays of nums that meet the following conditions: * The length of the subarray is k, and All the elements of the subarray are distinct. Return the maximum subarray sum of all the subarrays that meet the conditions . If no subarray meets the conditions, return 0. * 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 maximum_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::HashMap;
    let k = k as usize;
    let n = nums.len();
    let mut freq: HashMap<i32, usize> = HashMap::new();
    let mut window_sum = 0i64;
    let mut ans = 0i64;
    let mut distinct = 0usize;
    for i in 0..n {
      // add nums[i]
      let cnt = freq.entry(nums[i]).or_insert(0);
      if *cnt == 0 { distinct += 1; }
      *cnt += 1;
      window_sum += nums[i] as i64;
      // remove nums[i - k] if window too large
      if i >= k {
        let old = nums[i - k];
        window_sum -= old as i64;
        let cnt = freq.get_mut(&old).unwrap();
        *cnt -= 1;
        if *cnt == 0 { distinct -= 1; }
      }
      if i >= k - 1 && distinct == k {
        ans = ans.max(window_sum);
      }
    }
    ans
  }
}