湖北做網(wǎng)站系統(tǒng)哪家好百度貼吧網(wǎng)頁(yè)版
題目
給你一個(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