LeetCode 题解工作台
几乎唯一子数组的最大和
给你一个整数数组 nums 和两个正整数 m 和 k 。 请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。 如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。 子数组指的是一个数组中一段连续 非空 的…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以遍历数组 ，维护一个大小为 的窗口，用哈希表 统计窗口中每个元素的出现次数，用变量 统计窗口中所有元素的和。如果 中不同元素的个数大于等于 ，那么我们就更新答案 $ans = \max(ans, s)$。 遍历结束后，返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums 和两个正整数 m 和 k 。
请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
子数组指的是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [2,6,7,3,1,7], m = 3, k = 4 输出：18 解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。
示例 2：
输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3 输出：23 解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。
示例 3：
输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3 输出：0 解释：输入数组中不存在长度为k = 3的子数组含有至少m = 3个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。
提示：
1 <= nums.length <= 2 * 1041 <= m <= k <= nums.length1 <= nums[i] <= 109
解题思路
方法一：滑动窗口 + 哈希表
我们可以遍历数组 ，维护一个大小为 的窗口，用哈希表 统计窗口中每个元素的出现次数，用变量 统计窗口中所有元素的和。如果 中不同元素的个数大于等于 ，那么我们就更新答案 。
遍历结束后，返回答案即可。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
cnt = Counter(nums[:k])
s = sum(nums[:k])
ans = s if len(cnt) >= m else 0
for i in range(k, len(nums)):
cnt[nums[i]] += 1
cnt[nums[i - k]] -= 1
s += nums[i] - nums[i - k]
if cnt[nums[i - k]] == 0:
cnt.pop(nums[i - k])
if len(cnt) >= m:
ans = max(ans, s)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each element is added and removed from the window once. Space complexity is O(k) due to the hash map storing counts of elements in the current window. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Using a hash map or set to track distinct elements in the sliding window.
- question_mark
Ensuring incremental updates of sum and distinct count instead of recomputing from scratch.
- question_mark
Handling cases where subarrays do not meet the m distinct elements requirement.
常见陷阱
外企场景- error
Recomputing the sum or distinct count for every window instead of updating incrementally.
- error
Failing to correctly decrement counts in the hash map when elements leave the window.
- error
Not accounting for the case where no almost unique subarray exists and returning an incorrect value.
进阶变体
外企场景- arrow_right_alt
Change the distinct element threshold m to vary the almost uniqueness constraint.
- arrow_right_alt
Use a larger k relative to the array size to test sliding window efficiency under near-full coverage.
- arrow_right_alt
Optimize for streaming arrays where elements arrive one by one instead of a static array.