长度为 K 子数组中的最大和

难度: Medium

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

子数组的长度是 k，且
子数组中的所有元素 各不相同。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

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

示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：nums 中长度为 3 的子数组是：
- [4,4,4] 不满足全部条件，因为元素 4 出现重复。
因为不存在满足全部条件的子数组，所以返回 0 。

提示：

1 <= k <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Submission

运行时间: 130 ms

内存: 32.4 MB

from typing import List

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        max_sum = 0
        window = set()
        curr_sum = 0
        left = 0
        
        for right in range(len(nums)):
            while nums[right] in window:
                window.remove(nums[left])
                curr_sum -= nums[left]
                left += 1
            
            window.add(nums[right])
            curr_sum += nums[right]
            
            if right - left + 1 == k:
                max_sum = max(max_sum, curr_sum)
                window.remove(nums[left])
                curr_sum -= nums[left]
                left += 1
        
        return max_sum

Explain

题解采用了滑动窗口的策略来求解问题。首先，维护一个当前窗口内的元素集合（window）和窗口内元素的和（curr_sum）。通过双指针技术，右指针（right）遍历整个数组，将每个元素加入窗口。如果遇到窗口内已存在的元素（即有重复），则左指针（left）移动，并相应地从集合和当前和中移除左指针指向的元素，直到窗口内没有重复元素。每当窗口大小达到k时，比较当前窗口和（curr_sum）与历史最大和（max_sum），并更新最大和。之后，移动左指针缩小窗口，继续检查后续的可能窗口。通过这种方式，可以有效地找到所有满足条件的子数组，并计算出最大的子数组和。

时间复杂度: O(n)

空间复杂度: O(k)

from typing import List

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        max_sum = 0  # 记录遍历过程中的最大子数组和
        window = set()  # 窗口内的元素集合，用于快速检查元素是否重复
        curr_sum = 0  # 当前窗口内元素的和
        left = 0  # 滑动窗口的左边界
        
        for right in range(len(nums)):
            while nums[right] in window:  # 如果右边界的元素在窗口中已存在，表示有重复
                window.remove(nums[left])  # 从窗口中移除左边界的元素
                curr_sum -= nums[left]  # 更新窗口和
                left += 1  # 左边界向右移动
            
            window.add(nums[right])  # 将当前右边界的元素添加到窗口中
            curr_sum += nums[right]  # 更新窗口和
            
            if right - left + 1 == k:  # 当窗口大小达到k时
                max_sum = max(max_sum, curr_sum)  # 更新最大子数组和
                window.remove(nums[left])  # 移除窗口中的左边界元素，为下一次迭代做准备
                curr_sum -= nums[left]  # 更新窗口和
                left += 1  # 左边界向右移动
        
        return max_sum  # 返回找到的最大子数组和

Explore

在滑动窗口策略中，如果窗口内部出现重复元素，通常需要移动左指针来删除重复元素并减小窗口的大小，以恢复窗口的有效状态。移动右指针将使得窗口包含更多的元素，这可能导致更多的重复而不是解决问题。因此，移动左指针是为了尽快地去除重复元素，从而维持窗口内元素的唯一性。

在这种情况下，如果窗口大小仍然小于k且右指针已到达数组末尾，那么不可能再形成大小为k的窗口。因此，不需要继续增加窗口大小。这种情况通常表明数组长度小于k，或者因为重复元素的移除导致无法达到k大小的窗口。

当窗口大小正好等于k时，按照题目要求，我们需要计算并更新最大子数组和。移动左指针之后，可以立即开始探索新的可能性，即新的窗口组合。这样做可以确保每一种可能的k长度的子数组都被考虑到，同时保持窗口的动态移动，从而有效地找到最大的子数组和。等待直到找到更大的子数组和再移动左指针将会错过一些潜在的窗口配置，减少了算法的效率。