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
- Use a fixed-size window of length
kwith a frequency map and a running sum. - Slide the window one step at a time: add the entering element, remove the leaving one, and delete keys whose count reaches zero.
- The window is valid exactly when the map has
kdistinct keys, i.e. all elements are distinct. - 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner