题目描述

给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。

数组的 x-sum 计算按照以下步骤进行：

• 统计数组中所有元素的出现次数。
• 仅保留出现次数最多的前 x 个元素的每次出现。如果两个元素的出现次数相同，则数值 较大 的元素被认为出现次数更多。
• 计算结果数组的和。

注意，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。

返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum。

子数组 是数组内的一个连续 非空 的元素序列。

样例

输入：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。

输入：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

算法

(暴力) $O(nk \log k)$

1. 暴力遍历每个长度为 $k$ 的子数组。
2. 对于每个子数组，使用哈希表存储每个数字的出现次数。
3. 然后将数字按照出现次数排序，找到前 $x$ 大的数字计算答案。

时间复杂度

• 共有 $O(n)$ 个长度为 $k$ 的子数组，每个子数组都需要 $O(k \log k)$ 的时间计算答案。
• 故总时间复杂度为 $O(nk \log k)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表、出现次数的数组以及答案。

C++ 代码

class Solution {
public:
    vector<int> findXSum(vector<int>& nums, int k, int x) {
        const int n = nums.size();

        auto solve = [&](int l, int r) {
            unordered_map<int, int> h;
            for (int i = l; i <= r; i++)
                ++h[nums[i]];

            vector<pair<int, int>> s;
            for (const auto &[k, v] : h)
                s.emplace_back(v, k);

            sort(s.begin(), s.end());
            const int m = s.size();

            int res = 0;
            for (int i = m - 1; i >= max(0, m - x); i--)
                res += s[i].first * s[i].second;

            return res;
        };

        vector<int> ans(n - k + 1, 0);
        for (int i = 0; i < n - k + 1; i++)
            ans[i] = solve(i, i + k - 1);

        return ans;
    }
};