LeetCode 2841. 几乎唯一子数组的最大和

题目链接

2841. 几乎唯一子数组的最大和

题目描述

给你一个整数数组 nums 和两个正整数 m 和 k。请你返回 nums 中长度为 k 且几乎唯一的子数组的最大和。如果不存在这样的子数组，请返回 0。

几乎唯一子数组的定义：子数组中不同元素的数量至少为 m。

解法分析：滑动窗口法

核心思路

该解法采用滑动窗口技术，维护一个长度为 k 的固定窗口，通过以下步骤求解：

1. 遍历数组时，动态计算窗口内元素的和与不同元素的数量
2. 当窗口长度达到 k 时，判断不同元素数量是否≥m
3. 统计满足条件的窗口的最大和

代码实现

from collections import Counter
from typing import List

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        cnt = Counter()  # 记录窗口内元素的出现次数
        l = 0            # 左指针
        ans = 0          # 最大和（初始为0，无满足条件时返回0）
        s = 0            # 当前窗口的和
        
        for i in range(len(nums)):
            # 累加当前元素到窗口和
            s += nums[i]
            # 更新当前元素的计数
            cnt[nums[i]] += 1
            
            # 窗口长度不足k时，继续扩展
            if i + 1 < k:
                continue
            
            # 窗口长度达到k时，判断是否满足几乎唯一条件
            if len(cnt) >= m:
                ans = max(ans, s)
            
            # 滑动窗口：移除左边界元素
            s -= nums[l]
            cnt[nums[l]] -= 1
            # 若左边界元素计数为0，从计数器中删除
            if cnt[nums[l]] == 0:
                del cnt[nums[l]]
            # 左指针右移
            l += 1
        
        return ans

代码解析

1. 初始化变量：

   • cnt：Counter 对象，记录窗口内各元素的出现次数
   • l：滑动窗口左指针，初始为0
   • ans：满足条件的子数组的最大和，初始为0
   • s：当前窗口内元素的和，初始为0

2. 遍历数组：

   • 右指针 i 遍历每个元素，将当前元素 nums[i] 累加到窗口和 s 中
   • 同时更新 cnt 中该元素的计数（cnt[nums[i]] += 1）

3. 窗口判断逻辑：

   • if i + 1 < k：窗口长度不足 k 时（前 k-1 个元素），不进行判断，继续扩展窗口
   • 当窗口长度达到 k 时（i + 1 == k 及之后）：
     • 检查 cnt 的长度（即窗口内不同元素的数量）是否≥m
     • 若满足条件，更新 ans 为当前窗口和 s 与历史最大值中的较大者

4. 滑动窗口维护：

   • s -= nums[l]：从窗口和中减去左边界元素的值
   • cnt[nums[l]] -= 1：减少左边界元素的计数
   • 若左边界元素的计数变为0，从 cnt 中删除该元素（确保 len(cnt) 准确反映不同元素数量）
   • l += 1：左指针右移，保持窗口长度为 k

关键逻辑说明

• 几乎唯一判断：通过 len(cnt) ≥ m 实现，cnt 的长度即窗口内不同元素的数量
• 固定窗口滑动：窗口长度严格保持为 k，每次右指针移动后，左指针同步移动，避免重复计算
• 计数准确性：当元素计数归0时从 cnt 中删除，确保 len(cnt) 能正确反映当前窗口的不同元素数量

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。每个元素被左右指针各访问一次，Counter 的操作（增减计数、删除元素）均为 O(1) 平均复杂度。
• 空间复杂度：O(min(k, n))，cnt 中最多存储 k 个不同元素（窗口长度为 k），最坏情况下为 O(n)。

示例详解

以输入 nums = [2,6,7,3,1,7], m = 3, k = 4 为例：

1. 初始化：cnt = {}, l=0, ans=0, s=0

2. i=0（元素2）：

   • s = 0 + 2 = 2，cnt[2] = 1
   • i+1=1 < 4，不判断，继续

3. i=1（元素6）：

   • s = 2 + 6 = 8，cnt[6] = 1
   • i+1=2 < 4，不判断，继续

4. i=2（元素7）：

   • s = 8 + 7 = 15，cnt[7] = 1
   • i+1=3 < 4，不判断，继续

5. i=3（元素3）：

   • s = 15 + 3 = 18，cnt[3] = 1
   • i+1=4 == 4，窗口长度达标：
     • len(cnt) = 4 ≥ 3（元素2,6,7,3），满足条件
     • ans = max(0, 18) = 18
   • 滑动窗口：s -= 2（s=16），cnt[2] 减为0并删除，l=1

6. i=4（元素1）：

   • s = 16 + 1 = 17，cnt[1] = 1
   • 窗口元素：6,7,3,1（len(cnt)=4 ≥3）
   • ans = max(18, 17) = 18
   • 滑动窗口：s -= 6（s=11），cnt[6] 减为0并删除，l=2

7. i=5（元素7）：

   • s = 11 + 7 = 18，cnt[7] 变为2（原计数1+1）
   • 窗口元素：7,3,1,7（len(cnt)=3 ≥3）
   • ans = max(18, 18) = 18
   • 滑动窗口：s -=7（s=11），cnt[7] 减为1，l=3

8. 最终返回 18，符合示例逻辑。

复杂度分析

• 时间复杂度：O(n)，每个元素被左右指针各访问一次，Counter 操作平均为 O(1)。
• 空间复杂度：O(k)，cnt 最多存储 k 个不同元素（窗口长度为 k）。

总结

该解法通过滑动窗口技术高效解决了问题，核心优势在于：

1. 固定窗口维护：严格保持窗口长度为 k，避免冗余计算
2. 计数准确性：通过 Counter 实时跟踪不同元素数量，确保 len(cnt) 准确反映几乎唯一条件
3. 线性时间复杂度：双指针遍历使时间复杂度为 O(n)，适用于大规模数组

该思路可扩展到其他"固定长度子数组+元素约束"的问题，是滑动窗口结合计数的经典应用。