给你一个由 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

思路

  • 滑动窗口+数学+TreeSet

  • 滑动窗口+数学+Array+Arrays.sort()

  • AI优化版本（OpenAI-思考模式）

代码

  • 滑动窗口+数学+TreeSet

class Solution {
    public int[] findXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] answer = new int[n - k + 1];

        int[] counts = new int[51];
        int sum = 0;

        Set<Integer> set = new TreeSet<>((a1, a2) -> a2 - a1);
        for (int i = 0; i < k; i++) {
            int num = nums[i];
            if (counts[num] != 0) {
                set.remove(num + counts[num] * 100);
            }
            counts[num]++;
            set.add(num + counts[num] * 100);
        }
        int temp = x;
        Iterator<Integer> iterator1 = set.iterator();
        while (temp > 0 && iterator1.hasNext()) {
            int i = iterator1.next();
            sum += (i / 100) * (i % 100);
            temp--;
        }
        answer[0] = sum;
        for (int i = k; i < n; i++) {
            //删除
            int num = nums[i - k];
            set.remove(num + counts[num] * 100);
            counts[num]--;
            if (counts[num] != 0) {
                set.add(num + counts[num] * 100);
            }
            //添加
            int num2 = nums[i];
            if (counts[num2] != 0) {
                set.remove(num2 + counts[num2] * 100);
            }
            counts[num2]++;
            set.add(num2 + counts[num2] * 100);
            //计算
            temp = x;
            sum = 0;
            Iterator<Integer> iterator = set.iterator();
            while (temp > 0 && iterator.hasNext()) {
                int j = iterator.next();
                sum += (j / 100) * (j % 100);
                temp--;
            }
            answer[i - k + 1] = sum;
        }

        return answer;
    }
}

  • 滑动窗口+数学+Array+Arrays.sort()

class Solution {
    public int[] findXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] answer = new int[n - k + 1];
        int[] counts = new int[51];

        int index = 0;
        int idle = 0;
        Integer[] accounts = new Integer[51];
        //第一个窗口
        for (int i = 0; i < k; i++) {
            int num = nums[i];
            if (counts[num] != 0) {
                for (int j = 0; j < index; j++) {
                    if (accounts[j] == num + counts[num] * 100) {
                        accounts[j] = 0;
                    }
                }
                idle++;
            }
            counts[num]++;
            accounts[index++] = num + counts[num] * 100;
        }
        //排序
        Arrays.parallelSort(accounts, 0, index, Comparator.reverseOrder());
        //指针去掉闲置位
        index -= idle;
        //统计x个
        int temp1 = x;
        //防止数组下标越界
        int temp2 = index;
        //排序后遍历index
        int afterIndex = 0;
        int sum = 0;
        while (temp1 > 0 && temp2 > 0) {
            int tempNum = accounts[afterIndex++];
            sum += (tempNum / 100) * (tempNum % 100);
            temp1--;
            temp2--;
        }
        answer[0] = sum;
        for (int i = k; i < n; i++) {
            idle = 0;
            //删除
            int num = nums[i - k];
            for (int j = 0; j < index; j++) {
                if (accounts[j] == num + counts[num] * 100) {
                    accounts[j] = 0;
                }
            }
            idle++;
            counts[num]--;
            if (counts[num] != 0) {
                accounts[index++] = num + counts[num] * 100;
            }
            //添加
            int num2 = nums[i];
            if (counts[num2] != 0) {
                for (int j = 0; j < index; j++) {
                    if (accounts[j] == num2 + counts[num2] * 100) {
                        accounts[j] = 0;
                    }
                }
                idle++;
            }
            counts[num2]++;
            accounts[index++] = num2 + counts[num2] * 100;
            Arrays.parallelSort(accounts, 0, index, Comparator.reverseOrder());
            index -= idle;
            //计算
            temp1 = x;
            temp2 = index;
            afterIndex = 0;
            sum = 0;
            while (temp1 > 0 && temp2 > 0) {
                int tempNum = accounts[afterIndex++];
                sum += (tempNum / 100) * (tempNum % 100);
                temp1--;
                temp2--;
            }
            answer[i - k + 1] = sum;
        }
        return answer;
    }
}

  • AI优化版本（OpenAI-思考模式）

class Solution {
    public int[] findXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] answer = new int[n - k + 1];
        int[] counts = new int[51];

        // 初始化第一个窗口的计数
        for (int i = 0; i < k; i++) {
            counts[nums[i]]++;
        }
        answer[0] = calcTopX(counts, x);

        // 滑动窗口：移除旧值，添加新值，然后计算
        for (int i = k; i < n; i++) {
            counts[nums[i - k]]--;
            counts[nums[i]]++;
            answer[i - k + 1] = calcTopX(counts, x);
        }

        return answer;
    }

    // 根据当前 counts 数组，计算前 x 个 (count * num) 之和
    private int calcTopX(int[] counts, int x) {
        // 准备一个长度 51 的辅助数组：存储 counts[num] * 100 + num
        // 这样排序后，数值较大的元素（count 较大，或 count 相同但 num 较大）会排到后面
        int[] arr = new int[51];
        for (int num = 0; num <= 50; num++) {
            if (counts[num] > 0) {
                arr[num] = counts[num] * 100 + num;
            }
        }

        // 升序排序，最大值出现在末尾
        Arrays.sort(arr);

        int sum = 0;
        int taken = 0;
        // 从末尾开始，拿前 x 个有效值
        for (int i = 50; i >= 0 && taken < x; i--) {
            int v = arr[i];
            if (v == 0) break; // 后面没有更多有效条目
            int cnt = v / 100;
            int num = v % 100;
            sum += cnt * num;
            taken++;
        }
        return sum;
    }
}