2841. 几乎唯一子数组的最大和 Medium
给你一个整数数组 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 。
解题思路
输入：一个整数数组 nums 和两个正整数 m 和 k
输出：返回一个子数组的和，子数组长度要等于 k 并且不重复元素数量要 >= m
本题属于 固定长度滑动窗口类型 类型。
我们已知窗口长度为 k，这道题的难点在于要记录窗口内不重复元素的数量，满足数量 >= m 的窗口才记录答案
所以我们需要用一个 HashMap freq 记录窗口内元素的出现频率
我们可以从 0 开始扩张窗口长度，当大于 k 的时候意味着要缩小窗口，此时移除左端口并且更新窗口内元素频率
每次都判断当窗口长度为 k 并且不重复元素数量 >= m，满足条件则记录答案
代码实现
from typing import List
class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
# 初始化哈希表记录窗口内数字的频率
freq = {}
# 初始化最大和
max_sum = 0
# 初始化窗口左边界
left = 0
# 初始化窗口内元素的和
window_sum = 0
# 遍历数组，使用右指针 r 扩展窗口
for right in range(len(nums)):
num = nums[right]
# 更新窗口和
window_sum += num
# 更新频率表
freq[num] = freq.get(num, 0) + 1
# 如果窗口大小超过 k，收缩窗口
if right - left + 1 > k:
left_num = nums[left]
# 减去左边界元素的值
window_sum -= left_num
# 更新频率表
freq[left_num] -= 1
# 如果某个数字的频率为 0，删除该数字
if freq[left_num] == 0:
del freq[left_num]
# 左指针右移
left += 1
# 当窗口大小正好为 k 且唯一数字数量不少于 m 时，更新最大和
if right - left + 1 == k and len(freq) >= m:
max_sum = max(max_sum, window_sum)
return max_sum/**
* @param {number[]} nums
* @param {number} m - 至少有多少种不同元素
* @param {number} k - 子数组长度固定为 k
* @return {number}
*/
var maxSum = function(nums, m, k) {
let left = 0;
let total = 0;
let maxSum = 0;
const freq = new Map();
for (let right = 0; right < nums.length; right++) {
const num = nums[right];
total += num;
freq.set(num, (freq.get(num) || 0) + 1);
// 窗口大于 k 时，收缩左边界
if (right - left + 1 > k) {
const leftNum = nums[left];
total -= leftNum;
freq.set(leftNum, freq.get(leftNum) - 1);
if (freq.get(leftNum) === 0) freq.delete(leftNum);
left++;
}
// 窗口刚好为 k 且不同元素种类数 ≥ m
if (right - left + 1 === k && freq.size >= m) {
maxSum = Math.max(maxSum, total);
}
}
return maxSum;
};复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)