Leetcode 3321. Find X-Sum of All K-Long Subarrays II
1. 解题思路
这一题同样虽然是一道hard的题目，但也是比较常规的，就是通过一个滑动窗口不断地维护当前长度为k的滑动窗口内所有数字的出现次数，进而维护一个按照出现次数和大小从大到小排列的数组，最后使用这个数组维护top x的频次的数字的总和即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
n = len(nums)
cnt = Counter(nums[:k])
q = sorted([(-v, -k) for k, v in cnt.items()])
s = sum(it[0] * it[1] for it in q[:x])
ans = [s]
for i in range(k, n):
key, val = nums[i-k], cnt[nums[i-k]]
idx = bisect.bisect_left(q, (-val, -key))
q.pop(idx)
if idx < x:
s -= val * key
if x <= len(q):
s += q[x-1][0] * q[x-1][1]
cnt[key] -= 1
if cnt[key] > 0:
bisect.insort(q, (-val+1, -key))
nidx = bisect.bisect_left(q, (-val+1, -key))
if nidx < x:
s += key * (val-1)
if x < len(q):
s -= q[x][0] * q[x][1]
key, val = nums[i], cnt[nums[i]]
cnt[key] += 1
if val == 0:
bisect.insort(q, (-val-1, -key))
idx = bisect.bisect_left(q, (-val-1, -key))
if idx < x:
s += (val+1) * key
if x < len(q):
s -= q[x][0] * q[x][1]
else:
idx = bisect.bisect_left(q, (-val, -key))
q.pop(idx)
if idx < x:
s -= val * key
if x <= len(q):
s += q[x-1][0] * q[x-1][1]
bisect.insort(q, (-val-1, -key))
idx = bisect.bisect_left(q, (-val-1, -key))
if idx < x:
s += (val+1) * key
if x < len(q):
s -= q[x][0] * q[x][1]
ans.append(s)
return ans
提交代码评测得到：耗时3055ms，占用内存42.3MB。
原文地址：https://blog.csdn.net/codename_cys/article/details/142904428
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！