LeetCode 题解工作台
计算子数组的 x-sum II
给你一个由 n 个整数组成的数组 nums ，以及两个整数 k 和 x 。 数组的 x-sum 计算按照以下步骤进行： 统计数组中所有元素的出现次数。 仅保留出现频率最高的前 x 种元素。如果两种元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。 计算结果数组的和。 注意 ，如果数组中的不…
4
题型
3
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 统计窗口中每个元素的出现次数，用一个有序集合 存储窗口中出现次数最多的 个元素，用另一个有序集合 存储剩余的元素。 我们维护一个变量 表示 中元素的和。初始时，我们将前 个元素加入到窗口中，并且更新有序集合 和 ，并且计算 的值。如果 的大小小于 ，并且 不为空，我们就循环将 中的最大元素移动到 中，直到 的大小等于 ，过程中更新 的值。如果 的大…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。
数组的 x-sum 计算按照以下步骤进行：
- 统计数组中所有元素的出现次数。
- 仅保留出现频率最高的前
x种元素。如果两种元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。 - 计算结果数组的和。
注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。
返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum。
子数组 是数组内的一个连续 非空 的元素序列。
示例 1：
输入：nums = [1,1,2,2,3,4,2,3], k = 6, x = 2
输出：[6,10,12]
解释：
- 对于子数组
[1, 1, 2, 2, 3, 4]，只保留元素 1 和 2。因此，answer[0] = 1 + 1 + 2 + 2。 - 对于子数组
[1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。 - 对于子数组
[2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3。
示例 2：
输入：nums = [3,8,7,8,7,5], k = 2, x = 2
输出：[11,15,15,15,12]
解释：
由于 k == x，answer[i] 等于子数组 nums[i..i + k - 1] 的总和。
提示：
nums.length == n1 <= n <= 1051 <= nums[i] <= 1091 <= x <= k <= nums.length
解题思路
方法一：哈希表 + 有序集合
我们用一个哈希表 统计窗口中每个元素的出现次数，用一个有序集合 存储窗口中出现次数最多的 个元素，用另一个有序集合 存储剩余的元素。
我们维护一个变量 表示 中元素的和。初始时，我们将前 个元素加入到窗口中，并且更新有序集合 和 ，并且计算 的值。如果 的大小小于 ，并且 不为空，我们就循环将 中的最大元素移动到 中，直到 的大小等于 ，过程中更新 的值。如果 的大小大于 ，我们就循环将 中的最小元素移动到 中，直到 的大小等于 ，过程中更新 的值。此时，我们就可以计算出当前窗口的 ，添加到答案数组中。然后我们将窗口的左边界元素移出，更新 ，并且更新有序集合 和 ，以及 的值。继续遍历数组，直到遍历结束。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
相似题目：
class Solution:
def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
def add(v: int):
if cnt[v] == 0:
return
p = (cnt[v], v)
if l and p > l[0]:
nonlocal s
s += p[0] * p[1]
l.add(p)
else:
r.add(p)
def remove(v: int):
if cnt[v] == 0:
return
p = (cnt[v], v)
if p in l:
nonlocal s
s -= p[0] * p[1]
l.remove(p)
else:
r.remove(p)
l = SortedList()
r = SortedList()
cnt = Counter()
s = 0
n = len(nums)
ans = [0] * (n - k + 1)
for i, v in enumerate(nums):
remove(v)
cnt[v] += 1
add(v)
j = i - k + 1
if j < 0:
continue
while r and len(l) < x:
p = r.pop()
l.add(p)
s += p[0] * p[1]
while len(l) > x:
p = l.pop(0)
s -= p[0] * p[1]
r.add(p)
ans[j] = s
remove(nums[j])
cnt[nums[j]] -= 1
add(nums[j])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on maintaining the hash map and min-heap or ordered structure, roughly O(n log x) for all n-k+1 windows. Space complexity is O(k) for the hash map and auxiliary data structures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect clarification on handling fewer than x distinct elements in a window.
- question_mark
Check if candidate uses sliding window properly instead of recalculating sums naively.
- question_mark
Look for correct use of hash map or counting structure to track element frequencies.
常见陷阱
外企场景- error
Recomputing sums from scratch for each window instead of updating incrementally.
- error
Failing to handle windows with fewer than x distinct elements correctly.
- error
Neglecting edge cases when elements repeat and the smallest x distinct elements change.
进阶变体
外企场景- arrow_right_alt
Compute the largest x distinct elements instead of the smallest for each k-length subarray.
- arrow_right_alt
Return the average of the x smallest distinct elements for each window instead of the sum.
- arrow_right_alt
Use a circular array where windows wrap around the end of the array.