定长且至少包含M个不同元素的子数组最大和-LeetCode

2461. 定长且至少包含M个不同元素的子数组最大和

🎯 问题描述（来源于LeetCode）

描述：给你一个整数数组 nums 和两个正整数 m 和 k。请你找出长度为 k 且至少包含 m 个不同元素的子数组的最大和。
说明：

• 子数组是数组中连续的元素序列
• 如果不存在满足条件的子数组，则返回 0

示例：

• 示例 1：

输入：nums = [2,1,3], m = 2, k = 2
输出：4
解释：长度为 2 的子数组有 [2,1] 和 [1,3]，它们都包含至少 2 个不同元素。
[2,1] 的和为 3，[1,3] 的和为 4，因此返回 4。

• 示例 2：

输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
输出：0
解释：所有长度为 3 的子数组最多只包含 2 个不同元素，因此不存在满足条件的子数组。

💻 解题思路

思路1：定长滑动窗口 + 哈希表

思路1：代码实现

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        table = {}  # 哈希表记录窗口内各元素的频次
        count = 0   # 记录满足条件的子数组的最大和
        count_num = 0  # 记录当前窗口内元素的总和
        
        for i, num in enumerate(nums):
            # 1. 扩展窗口：将当前元素加入哈希表和总和
            if num not in table:
                table[num] = 1
            else:
                table[num] += 1
            count_num += num
            
            # 计算当前窗口的左边界
            left = i - k + 1
            
            # 2. 窗口未形成：如果左边界小于0，说明元素不足k个，跳过判断
            if left < 0:
                continue
            
            # 3. 窗口已形成：判断不同元素个数是否满足条件
            if len(table) >= m:  # len(table) 表示不同元素的个数
                count = max(count, count_num)
            
            # 4. 收缩窗口：移除最左边的元素
            out_num = nums[left]
            table[out_num] -= 1
            if table[out_num] == 0:
                del table[out_num]  # 频次为0时从哈希表中删除
            count_num -= out_num
            
        return count

思路1：📊 性能分析

复杂度验证：

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 nums 的长度。代码只对数组进行了一次线性遍历，每个元素最多被访问两次（一次加入窗口，一次移出窗口）。
  • 哈希表的插入、删除和查询操作均为 $O(1)$。
• 空间复杂度：$O(min(k, distinct))$
  • 哈希表最多存储窗口内不同元素的个数，最坏情况下为 $O(k)$。
  • 其他变量均为常数空间。

思考

1. 哈希表的巧妙应用：
   • 使用哈希表 table 记录窗口内每个元素的出现频次
   • 通过 len(table) 可以直接获取当前窗口内不同元素的个数
   • 当某个元素的频次降为0时，及时从哈希表中删除，保证 len(table) 准确反映不同元素个数
2. 滑动窗口的精髓：
   • 维护一个固定长度为 k 的滑动窗口
   • 通过 count_num 变量避免重复计算子数组和
   • 每次窗口滑动时，只更新被移除和新加入的元素信息
3. 边界处理：
   • 利用 left = i - k + 1 < 0 来处理数组前 k-1 个元素的初始化阶段
   • 初始时 count = 0，如果找不到满足条件的子数组，自然返回0
4. 优化空间：
   • 可以使用 collections.defaultdict(int) 简化哈希表操作
   • 或者使用 Counter 类来自动处理元素频次统计

扩展思考：

• 如果题目要求找出所有满足条件的子数组，可以修改代码收集所有符合条件的子数组
• 如果 m 的值很大，可能需要考虑提前终止的优化策略
• 对于大数据量场景，可以考虑并行处理的优化方案

总结：
这道题综合考察了滑动窗口和哈希表的应用，是典型的"定长窗口+条件判断"问题。通过维护窗口内元素频次和总和，我们能够在一次遍历中高效解决问题。