What is the key strategy for Maximum Sum of Distinct Subarrays With Length K?

Use a sliding window of size k and a hash set to ensure elements are distinct while tracking the sum efficiently.

How do I handle duplicates in the subarray efficiently?

Remove the element leaving the window from the hash set and skip any window where a duplicate exists in the set.

What if no subarray of length k has distinct elements?

Return 0 because no valid subarray meets the distinct-element requirement.

Why is the sliding window approach preferred here?

It allows O(1) updates for sum and hash set operations per window shift, giving O(N) overall time.

Can this method be adapted for different subarray lengths?

Yes, by changing k and maintaining the same sliding window with hash set logic to track distinct elements.

#2461

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

长度为 K 子数组中的最大和

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：子数组的长度是 k ，且子数组中的所有元素各不相同。返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。子数组是数组中一段连续非空的元素序列。示例 1：…

数组哈希表滑动窗口

题目描述

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

子数组的长度是 k，且
子数组中的所有元素 各不相同。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

子数组 是数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

提示：

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：滑动窗口 + 哈希表

我们维护一个长度为 $k$ 的滑动窗口，用哈希表 $cnt$ 记录窗口中每个数字出现的次数，用变量 $s$ 记录窗口中所有数字的和。每次滑动窗口，如果窗口中的数字都不重复，那么更新答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums[:k])
        s = sum(nums[:k])
        ans = s if len(cnt) == k else 0
        for i in range(k, len(nums)):
            cnt[nums[i]] += 1
            cnt[nums[i - k]] -= 1
            if cnt[nums[i - k]] == 0:
                cnt.pop(nums[i - k])
            s += nums[i] - nums[i - k]
            if len(cnt) == k:
                ans = max(ans, s)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(N) because each element enters and leaves the window at most once. Space complexity is O(N) due to the hash set tracking distinct elements.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Can you explain which elements change when the window moves by one position?
question_mark
How do you efficiently check for duplicates in each subarray?
question_mark
What data structure ensures constant-time add and remove for sliding windows?

warning

常见陷阱

外企场景

error
Forgetting to remove the outgoing element from the hash set when sliding the window.
error
Recomputing the sum from scratch instead of maintaining a running sum.
error
Including subarrays with repeated elements when only distinct sums are allowed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find maximum sum of subarrays of length k allowing at most one duplicate.
arrow_right_alt
Compute maximum sum for subarrays of any length with distinct elements.
arrow_right_alt
Return the subarray itself rather than just the maximum sum.

help

常见问题

外企场景

继续练习

#2537 统计好子数组的数目 #2653 滑动子数组的美丽值 #2260 必须拿起的最小连续卡牌数