⚡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

中文速览与面试要点

长度为 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) &gt;= 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