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
中文速览与面试要点
长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k。请你从 nums 中满足下述条件的全部子数组中找出 最大 子数组和:子数组的长度是 k,且子数组中的所有元素 互不相同 。返回满足题意的最大元素和。如果不存在这样的子数组,返回 0。约束:1 ≤ k ≤ nums.length ≤ 10^5;1 ≤ nums[i] ≤ 10^5。
核心要点
- 定长窗口 + 计数去重(标准解) :维护长度为 k 的窗口和 cur 与窗口内元素的计数 cnt 。
- 合法性判定 :窗口内所有元素互不相同等价于 len(cnt) == k (前提是计数降为 0 时必须删除该键)。
- 滚动更新 :加入新元素、移除滑出元素;移除后计数为 0 则删除该键。
- 取最大 :仅在窗口合法时用 cur 更新答案。
常见陷阱
- 不删除零计数键 : len(cnt) 会小于 k,导致合法窗口被误判为非法。这是本题第一大坑。
- 判定条件写成 len(cnt) >= k :窗口长度恰好为 k,因此互不相同等价于 len(cnt) == k 。
- 忘记在滑出时同步减去 cur :窗口和会偏大。
- 用 len(set(nums[i-k+1:i+1])) 每次判重 :切片 + 建集合是 O(k),整体 O(n · k)。
参考实现
from collections import defaultdict
class Solution:
def maximumSubarraySum(self, nums: list[int], k: int) -> int:
cnt = defaultdict(int)
cur = 0
best = 0
for i, x in enumerate(nums):
cur += x
cnt[x] += 1
if i >= k: # 移除滑出窗口的元素
out = nums[i - k]
cur -= out
cnt[out] -= 1
if cnt[out] == 0:
del cnt[out] # 关键:清理零计数键
if i >= k - 1 and len(cnt) == k: # 窗口内元素互不相同
if cur > best:
best = cur
return best