LeetCode 每日一题笔记

0. 前言

• 日期：2025.11.04
• 题目：3318.计算子数组的x-sum
• 难度：简单
• 标签: 数组 哈希表 滑动窗口

1. 题目理解

问题描述：
给你一个由 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 = 6。
• 对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4 = 10。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。
• 对于子数组 [2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3 = 12。

2. 解题思路

核心观察

• 需对每个长度为k的连续子数组单独计算x-sum，因此需要遍历所有可能的子数组。
• 计算x-sum的关键是统计元素出现次数并按规则筛选前x个高频元素：次数高的优先，次数相同则数值大的优先。

算法步骤

1. 遍历所有子数组：通过外层循环 i 遍历每个长度为k的子数组的起始位置（i 从0到 n-k）。
2. 统计子数组元素次数：对每个子数组，用哈希表 countMap 统计其中每个元素的出现次数。
3. 排序筛选元素：将哈希表的键值对转换为列表，按“出现次数降序、数值降序”的规则排序，得到前x个（或全部）高频元素。
4. 计算x-sum：累加前x个元素的“值×出现次数”的乘积，作为当前子数组的x-sum。

3. 代码实现

class lc3600_lc3699.lc3660.Solution {
    public int[] findXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] answer = new int[n - k + 1];
        
        for (int i = 0; i <= n - k; i++) {
            // 统计当前子数组的元素出现次数
            Map<Integer, Integer> countMap = new HashMap<>();
            for (int j = i; j < i + k; j++) {
                countMap.put(nums[j], countMap.getOrDefault(nums[j], 0) + 1);
            }
            
            // 将元素按“出现次数降序、数值降序”排序
            List<Map.Entry<Integer, Integer>> list = new ArrayList<>(countMap.entrySet());
            list.sort((a, b) -> {
                if (a.getValue().equals(b.getValue())) {
                    return b.getKey() - a.getKey(); // 次数相同，数值大的排前面
                }
                return b.getValue() - a.getValue(); // 次数多的排前面
            });
            
            // 计算x-sum
            int sum = 0;
            int take = Math.min(x, list.size()); // 若不同元素少于x个，取全部
            for (int j = 0; j < take; j++) {
                Map.Entry<Integer, Integer> entry = list.get(j);
                sum += entry.getKey() * entry.getValue();
            }
            
            answer[i] = sum;
        }
        
        return answer;
    }
}

4. 代码优化说明

• 哈希表统计优化：使用 getOrDefault 方法简化次数统计逻辑，避免手动判空。
• 排序逻辑优化：自定义 Comparator 明确“次数降序、数值降序”的排序规则，确保筛选逻辑正确。
• 边界处理优化：通过 Math.min(x, list.size()) 处理“不同元素少于x个”的特殊情况，保证逻辑鲁棒性。

5. 复杂度分析

• 时间复杂度：$O((n-k+1)\times (k+m\log m))$，其中n是数组长度，k是子数组长度，m是子数组中不同元素的数量。
  • 遍历所有子数组：$O(n-k+1)$；
  • 每个子数组统计次数：$O(k)$；
  • 每个子数组排序：$O(m\log m)$（m最多为k）。
• 空间复杂度：$O(k+m)$，哈希表和排序列表的额外空间开销（m为子数组中不同元素的数量，最多为k）。

6. 总结

本题的核心是对每个子数组进行“次数统计 + 排序筛选 + 求和”的流程。该解法逻辑直观、易于理解，适合题目数据规模不大的场景。