几乎唯一子数组的最大和

标签: 数组 哈希表 滑动窗口

难度: Medium

给你一个整数数组 nums 和两个正整数 m 和 k 。

请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。

如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。

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

示例 1：

输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。

示例 2：

输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
输出：23
解释：总共有 5 个长度为 k = 3 的几乎唯一子数组。分别为 [5, 9, 9] ，[9, 9, 2] ，[9, 2, 4] ，[2, 4, 5] 和 [4, 5, 4] 。这些子数组中，和最大的是 [5, 9, 9] ，和为 23 。

示例 3：

输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
输出：0
解释：输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 109

Submission

运行时间: 129 ms

内存: 19.1 MB

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        ds = {}
        
        
        for i in range(k):
            ds[nums[i]] = ds.get(nums[i], 0) + 1
        
        s = sum(nums[0:k])
        res = 0
        if len(ds) >= m: res = s
        
        for i in range(0, len(nums)-k):
            s -= nums[i]
            s += nums[i+k]
            ds[nums[i]] -= 1
            ds[nums[i+k]] = ds.get(nums[i+k], 0) + 1
            if ds[nums[i]] == 0: ds.pop(nums[i])
            if len(ds) >= m:
                res = max(res, s)
            
        return res

Explain

该题解采用了滑动窗口和哈希表的方法。首先，使用哈希表`ds`来记录窗口内元素的出现次数，以及变量`s`来记录窗口内元素的和。窗口的初始位置是数组的前`k`个元素。然后，遍历数组，每次向右滑动窗口一位，更新窗口内的元素和以及哈希表的内容。如果在滑动后的窗口中，哈希表的大小（即窗口内不同元素的数量）大于等于`m`，那么就尝试更新最大和`res`。最终返回得到的最大和`res`，如果没有符合条件的子数组，则返回`0`。

时间复杂度: O(n)

空间复杂度: O(k)

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        ds = {} # 存储窗口内元素及其出现次数
        
        # 初始化窗口和窗口内元素的和
        for i in range(k):
            ds[nums[i]] = ds.get(nums[i], 0) + 1
        
        s = sum(nums[0:k]) # 窗口的初始和
        res = 0
        if len(ds) >= m: res = s # 更新结果
        
        # 滑动窗口
        for i in range(0, len(nums)-k):
            s -= nums[i] # 移除窗口最左侧元素的和
            s += nums[i+k] # 添加新元素到窗口的和
            ds[nums[i]] -= 1 # 更新哈希表
            ds[nums[i+k]] = ds.get(nums[i+k], 0) + 1 # 更新哈希表
            if ds[nums[i]] == 0: ds.pop(nums[i]) # 如果某元素计数为0，从哈希表中移除
            if len(ds) >= m: # 检查窗口是否几乎唯一
                res = max(res, s) # 更新最大和
        
        return res # 返回最大和

Explore

在使用滑动窗口处理数组时，哈希表用于记录窗口内每个元素的出现次数。当窗口向右移动时，窗口最左侧的元素被移除，其对应在哈希表中的计数减一。如果该元素的频率降为零，则意味着它不再出现在当前的窗口内。为了保持哈希表的准确性和减少空间占用，将频率为0的元素从哈希表中删除是必要的。这样可以确保哈希表只包含窗口内存在的元素，同时减少无用数据的存储，提高算法效率。

更新窗口和时，移除最左侧元素和添加新元素是为了保持窗口的长度恒定为k。每次滑动窗口向右移动一位，最左侧的元素被移出窗口，同时数组中的下一个元素加入窗口的右侧。这种操作确保了每次移动后窗口中的元素总数仍然是k个，从而维持了窗口的固定长度。

在题解中，子数组是否符合条件是基于窗口内不同元素的数量是否达到或超过了m来判断。如果在整个数组遍历结束后，没有任何一个窗口的不同元素数量满足大于等于m的条件，那么意味着不存在符合条件的子数组，此时应返回0。具体实现中，可以通过设置一个初始值res=0，并只有在找到至少一个满足条件的窗口时才更新这个值，如果遍历完数组后res仍为0，则说明没有符合条件的子数组。

题目要求寻找的是几乎唯一的子数组，其中‘几乎唯一’是通过窗口内不同元素的数量是否大于等于m来定义的。只有当窗口内不同元素的数量达到或超过m时，该窗口的元素组合才符合题目的‘几乎唯一’的要求。因此，只在这种情况下更新最大和是合适的，这样可以确保只考虑符合题目条件的子数组，避免不必要的计算和错误的结果更新。