⚡Flashcard Drill➔
NeetCode #248LC-2461MediumSliding Window
← Back to All Problems

#248 · #2461 · Maximum Sum of Distinct Subarrays With Length K(长度为 K 子数组中的最大和)

📌 Problem Statement & Constraints

You are given an integer array nums and an integer k. Find the maximum subarray sum for a subarray of length k where all elements are distinct. Return 0 if no such subarray exists. Constraints: 1 <= k <= nums.length <= 10^5, 1 <= nums[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Use a fixed-size window of length k with a frequency map and a running sum.
  2. Slide the window one step at a time: add the entering element, remove the leaving one, and delete keys whose count reaches zero.
  3. The window is valid exactly when the map has k distinct keys, i.e. all elements are distinct.
  4. Track the maximum valid sum.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        from collections import Counter
        n = len(nums)
        if k > n:
            return 0
        cnt = Counter(nums[:k])
        total = sum(nums[:k])
        res = total if len(cnt) == k else 0
        for i in range(k, n):
            cnt[nums[i]] += 1          # entering
            total += nums[i]
            out = nums[i - k]
            cnt[out] -= 1              # leaving
            total -= out
            if cnt[out] == 0:
                del cnt[out]           # keep the distinct count accurate
            if len(cnt) == k:
                res = max(res, total)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) average map operations.
💾 Space Complexity
O(k) for the frequency map.

⚠️ Interview Pitfalls & Follow-ups

  • Checking distinctness with a set: a set cannot represent multiplicities, so the leaving-element bookkeeping would be wrong.
  • Not deleting zero-count keys: len(cnt) would overcount the distinct values and valid windows would be missed.
  • Forgetting to initialise the result from the first window: the slide loop starts at index k, so the first window must be evaluated separately.
  • Using a variable-length window: the subarray length is fixed at exactly k.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems