leetcode | 3318. 计算子数组的 x-sum I

给你一个由 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] 的总和。

 

提示：

1 <= n == nums.length <= 50
1 <= nums[i] <= 50
1 <= x <= k <= nums.length

要解决这个问题，我们需要计算数组中每个长度为 k 的子数组的 x-sum。x-sum 的计算规则是：保留子数组中出现次数最多的前 x 个元素（若次数相同则保留数值较大的元素），并计算这些元素的总和。

方法思路

1. 遍历所有子数组：对于给定数组，依次截取所有长度为 k 的连续子数组。
2. 统计元素出现次数：对每个子数组，使用计数器统计其中每个元素的出现次数。
3. 排序元素：根据元素的出现次数（降序）和元素值（降序，若次数相同）对元素进行排序，以确定需要保留的前 x 个元素。
4. 计算 x-sum：对排序后选出的前 x 个元素，计算它们在子数组中的总出现次数与各自值的乘积之和，即为该子数组的 x-sum。

代码实现

from collections import Counter
from typing import List

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        result = []
        # 遍历所有长度为k的子数组
        for i in range(n - k + 1):
            # 截取当前子数组
            subarray = nums[i:i + k]
            # 统计子数组中各元素的出现次数
            count = Counter(subarray)
            # 排序规则：先按出现次数降序，次数相同则按元素值降序
            sorted_elements = sorted(count.keys(), key=lambda num: (-count[num], -num))
            # 选取前x个元素（若不同元素少于x个则全部选取）
            selected = sorted_elements[:x]
            # 计算这些元素的总贡献（x-sum）
            x_sum = sum(num * count[num] for num in selected)
            result.append(x_sum)
        return result

解释

1. 遍历子数组：通过循环遍历数组，每次截取从索引 i 开始、长度为 k 的子数组（i 的范围是 0 到 n - k，确保子数组不越界）。
2. 统计次数：使用 Counter 工具快速统计子数组中每个元素的出现次数，得到一个字典（键为元素，值为出现次数）。
3. 排序元素：对元素进行排序时，使用自定义排序键 (-count[num], -num)，确保先按出现次数降序排列，次数相同则按元素值降序排列。
4. 计算 x-sum：从排序后的元素中选取前 x 个，计算它们的总贡献（每个元素的值乘以其在子数组中的出现次数之和），并将结果存入结果列表。