【定长滑动窗口】【刷题笔记】

标题：《2841. 几乎唯一子数组的最大和问题解析》

在本文中，我们将深入探讨力扣上的 2841. 几乎唯一子数组的最大和这一问题，并详细解析两种不同的解答思路。

一、题目描述

给定一个整数数组 nums 和两个正整数 m 和 k。要求返回 nums 中长度为 k 的几乎唯一子数组的最大和，如果不存在几乎唯一子数组，则返回 0。这里，如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是几乎唯一子数组。子数组指的是一个数组中一段连续非空的元素序列。

二、解答思路

（一）第一种解答思路

以下是代码实现：

from typing import List
from collections import Counter
class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        ans = 0
        s = sum(nums[:k - 1])  # 先统计 k - 1 个数
        cnt = Counter(nums[:k - 1])
        for out, in_ in zip(nums, nums[k - 1:]):
            s += in_  # 再添加一个数就是 k 个数了
            cnt[in_] += 1
            if len(cnt) >= m:
                ans = max(ans, s)

            s -= out  # 下一个子数组不包含 out，移出窗口
            cnt[out] -= 1
            if cnt[out] == 0:
                del cnt[out]
        return ans

1. 整体思路：
   • 首先计算初始窗口（前 k - 1 个数）的和 s 以及使用 Counter 统计这 k - 1 个数中每个数出现的次数，存储在 cnt 中。
   • 然后通过滑动窗口的方式，利用 zip 函数同时遍历原数组 nums 和从第 k - 1 个位置开始的子数组 nums[k - 1:]。在每次滑动时，将新进入窗口的数加入和 s 中，并更新 cnt 计数器，接着判断当前窗口内不同元素的数量是否满足至少 m 个，如果满足则更新最大和 ans。之后将离开窗口的数从和 s 中减去，并更新 cnt 计数器，如果该数的计数变为 0，则从 cnt 中删除该元素。
2. 涉及的 Python 语法知识点：
   • Counter：Counter 是 collections 模块中的一个类，它是一个字典的子类，用于方便地统计可迭代对象中每个元素出现的次数。例如，Counter([1, 2, 2, 3]) 会返回一个 Counter 对象 {1: 1, 2: 2, 3: 1}，其中键是元素，值是该元素出现的次数。在本题中，它用于统计窗口内元素的出现次数，以便判断不同元素的数量是否满足条件。
   • zip：zip 函数用于将多个可迭代对象中对应的元素打包成一个个元组，然后返回一个由这些元组组成的可迭代对象。在本题中，for out, in_ in zip(nums, nums[k - 1:]) 的作用是同时遍历原数组 nums 和从第 k - 1 个位置开始的子数组 nums[k - 1:]，在每次循环中，out 是即将离开窗口的元素，in_ 是新进入窗口的元素，这样可以方便地进行窗口的滑动操作并处理相关逻辑。

（二）第二种解答思路

以下是代码实现：

from typing import List
class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        n = len(nums)
        ans = 0      # 最终答案 几乎唯一(m 个互异元素)子数组（k 长度）的最大值
        sum_num = 0  # 当前窗口（当前子数组）加和
        cnt = {}     # 定义字典作为计数器，记录窗口内有无重复

        # 初始化窗口
        for i in range(k - 1):
            sum_num += nums[i]  # 计算加和
            if nums[i] in cnt:  # 字典计数器
                cnt[nums[i]] += 1
            else:
                cnt[nums[i]] = 1

        # 滑动窗口，
        for i in range(k - 1, n):
            # 1.进入窗口（本次操作前，窗口长度差一格）
            sum_num += nums[i]  # 加和
            if nums[i] in cnt:     # 字典计数器，
                cnt[nums[i]] += 1   # 当前元素出现过，cnt 字典长度不变，对应键值对改变
            else:                    # 没出现过，cnt 字典长度加 1
                cnt[nums[i]] = 1

            # 2.更新答案，前提是满足几乎唯一，也就是至少有 m 个互异元素
            if len(cnt) >= m:         # cnt 长度>=m
                ans = max(ans, sum_num)

            # 3.（谁？i -（k - 1）位置的元素）退出窗口，
            out = nums[i - k + 1]   # 就是它退出了！
            sum_num -= out          # 先加和中去掉它
            cnt[out] -= 1           # 计数器中扣掉 1
            if cnt[out] == 0:
                del cnt[out]       # 如果扣完变成了 0，del 删掉字典中这个元素
        return ans

1. 整体思路：
   • 先初始化一个长度为 k - 1 的窗口，计算其和 sum_num 并统计窗口内元素出现次数到字典 cnt 中。
   • 接着进行滑动窗口操作，在每次循环中，先将新元素加入窗口，更新和 sum_num 与计数器 cnt。然后判断当前窗口内不同元素数量是否满足至少 m 个，如果满足则更新最大和 ans。最后将离开窗口的元素从和 sum_num 中减去，并更新计数器 cnt，若该元素计数变为 0，则从 cnt 中删除。

三、总结

两种解答思路都采用了滑动窗口的方法来解决问题。第一种思路借助了 Counter 和 zip 等 Python 内置工具和函数，使得代码更加简洁高效，在统计元素出现次数和处理窗口滑动时更加方便。第二种思路则是较为传统的手动实现窗口内元素计数和窗口滑动操作，虽然代码相对第一种略显繁琐，但逻辑更加直观，有助于深入理解滑动窗口算法以及相关数据结构（如字典）在算法中的应用。在实际编程中，可以根据具体情况选择合适的方法来解决类似问题。

希望通过本文的解析，读者能够对 2841. 几乎唯一子数组的最大和这一问题有更深入的理解，并能熟练掌握滑动窗口算法以及相关 Python 语法知识在算法中的应用。

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

这题比上一题还简单！
class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        sum_num = 0
        cnt = {}

        for i in range(n):
            # 1.进入窗口
            sum_num += nums[i]       # 加和
            if nums[i] in cnt:       # 调用当前窗口，每个元素数量记录器cnt
                cnt[nums[i]] += 1
            else:
                cnt[nums[i]] = 1    # 出现新元素，cnt长度加1
            if i < k - 1:           # 如果i没到k-1，也就是窗口长度没够时
                continue
            
            # 2.更新答案        # 前提是cnt长度与子数组长度k相等！表示当前窗口所有元素各不相同！
            if len(cnt) == k:
                ans = max(ans, sum_num)
            
            # 3.退出窗口       # 谁？i-(k-1)  # 加和删掉该位置元素  # 记录器删掉一次该元素！
            out = nums[i - k + 1]
            sum_num -= out
            cnt[out] -= 1
            if cnt[out] == 0:
                del cnt[out]
            
        return ans