日期: 2025 年 11 月 4 日

目标

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

暴力解法是直接模拟，使用哈希表记录 元素值与出现次数，使用优先队列保存，取出现次数前 x 大的所有元素和。

代码

/**
 * @date 2025-11-04 0:27
 */
public class FindXSum3318 {

    public int[] findXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            Map<Integer, Counter> map = new HashMap<>();
            PriorityQueue<Counter> q = new PriorityQueue<>((a, b) -> {
                int compare = b.cnt - a.cnt;
                if (compare != 0) {
                    return compare;
                }
                return b.digit - a.digit;
            });
            for (int j = i; j < i + k; j++) {
                map.putIfAbsent(nums[j], new Counter(nums[j], 0));
                map.get(nums[j]).cnt++;
            }
            for (Counter value : map.values()) {
                q.offer(value);
            }
            int c = x;
            while (c > 0 && !q.isEmpty()) {
                Counter counter = q.poll();
                res[i] += counter.cnt * counter.digit;
                c--;
            }
        }
        return res;
    }

    public class Counter {
        int digit;
        int cnt;

        public Counter(int digit, int cnt) {
            this.digit = digit;
            this.cnt = cnt;
        }

        public Counter() {
        }
    }

}

性能