題目

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 。請(qǐng)你從 nums 中滿足下述條件的全部子數(shù)組中找出最大子數(shù)組和：

子數(shù)組的長(zhǎng)度是 k，且
子數(shù)組中的所有元素 各不相同 。
返回滿足題面要求的最大子數(shù)組和。如果不存在子數(shù)組滿足這些條件，返回 0 。

子數(shù)組 是數(shù)組中一段連續(xù)非空的元素序列。

示例 1：
輸入：nums = [1,5,4,2,9,9,9], k = 3
輸出：15
解釋：nums 中長(zhǎng)度為 3 的子數(shù)組是：

• [1,5,4] 滿足全部條件，和為 10 。
• [5,4,2] 滿足全部條件，和為 11 。
• [4,2,9] 滿足全部條件，和為 15 。
• [2,9,9] 不滿足全部條件，因?yàn)樵?9 出現(xiàn)重復(fù)。
• [9,9,9] 不滿足全部條件，因?yàn)樵?9 出現(xiàn)重復(fù)。
  因?yàn)?15 是滿足全部條件的所有子數(shù)組中的最大子數(shù)組和，所以返回 15 。

示例 2：
輸入：nums = [4,4,4], k = 3
輸出：0
解釋：nums 中長(zhǎng)度為 3 的子數(shù)組是：

• [4,4,4] 不滿足全部條件，因?yàn)樵?4 出現(xiàn)重復(fù)。
  因?yàn)椴淮嬖跐M足全部條件的子數(shù)組，所以返回 0 。

提示：

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105

題目鏈接

我的思路

維護(hù)一個(gè)sub數(shù)組記錄窗口內(nèi)數(shù)字，用集合判斷是否重復(fù)

思路不足：
會(huì)超時(shí)

我的代碼

class Solution:def maximumSubarraySum(self, nums: List[int], k: int) -> int:max_sub = 0sub = []for i,n in enumerate(nums):sub.append(n)if i < k-1:continueif 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 = 0cnt = Counter(nums[:k-1])s = sum(nums[:k-1])for i,o in zip(nums[k-1:],nums):cnt[i]+=1s+=iif len(cnt)==k:ms = max(ms,s)cnt[o]-=1if cnt[o]==0:del cnt[o]s-=oreturn ms