长度为k子数组中的最大和-LeetCode

2461.长度为k子数组中的最大和

🎯 问题描述（来源于LeetCode）

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

1. 子数组的长度是 k。
2. 子数组中的所有元素各不相同（互不相同）。

如果不存在满足这些条件的子数组，返回 0。

说明：

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

• 核心逻辑：长度为 k 的子数组中所有元素各不相同，等价于该子数组中不同元素的个数等于 k。

• 示例：

• 示例 1：

输入：nums = [1,2,3,4,5], k = 3
输出：12
解释：子数组 [3,4,5] 的和为 12，长度为 3，且所有元素互不相同。

• 示例 2：

输入：nums = [1,2,2,1], k = 3
输出：0
解释：长度为 3 的子数组有 [1,2,2] 和 [2,2,1]，它们都包含重复元素 2，因此不存在满足条件的子数组。

💻 解题思路

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

思路1：代码实现

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

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 nums 的长度。代码对数组进行了一次线性遍历，每个元素被加入和移出窗口各一次。哈希表的插入、删除和查询操作在平均情况下可视为 $O(1)$。
• 空间复杂度：$O(k)$
  • 哈希表 table 最多存储窗口内 $k$ 个元素的频次信息。

思考

1. 哈希表的作用：

   • 代码利用字典 table 动态维护窗口内元素的频次。
   • len(table) 实时反映了当前窗口内不同元素的数量。这是判断是否存在重复元素的关键依据。

2. 滑动窗口技巧：

   • 代码使用 left = i - k + 1 来计算窗口的左边界。
   • 通过 if left < 0: continue 跳过数组起始阶段窗口未填满的情况，这是一种简洁的定长窗口处理方式。