[LeetCode-Python版] 定长滑动窗口8——2461. 长度为 K 子数组中的最大和
题目
给你一个整数数组 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 <= 105
- 1 <= nums[i] <= 105
题目链接
我的思路
维护一个sub数组记录窗口内数字,用集合判断是否重复
思路不足:
会超时
我的代码
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
max_sub = 0
sub = []
for i,n in enumerate(nums):
sub.append(n)
if i < k-1:
continue
if len(set(sub)) == len(sub):
max_sub = max(max_sub,sum(sub))
sub.pop(0)
return max_sub
题解思路
用哈希表
参考代码
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
ms = 0
cnt = Counter(nums[:k-1])
s = sum(nums[:k-1])
for i,o in zip(nums[k-1:],nums):
cnt[i]+=1
s+=i
if len(cnt)==k:
ms = max(ms,s)
cnt[o]-=1
if cnt[o]==0:
del cnt[o]
s-=o
return ms