3318. Find X-Sum of All K-Long Subarrays I

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */

这是一道上限极高的简单题，题目给我们一个数字数组 nums，要求我们求出对该数组一系列操作之后的结果

一系列操作说明如下：

1. 将该数组划分为多个下标范围为 [i, ..., i+k] 的子数组
2. 计算该子数组每个元素出现的频率
3. 将出现个数排序，取最高的 x 个元素求和（如果有相同出现频率的元素则取元素值大的）
4. 将求和结果放入一个结果数组中，最后遍历完所有子数组后返回该结果数组

这题有一个极为关键的约束条件：1 <= nums[i] <= 50 这使得我们可以尝试一些暴力的解法

解题思路

简单题简单做，直接暴力梭哈，困难的优化方案留到后面 3321 题再做～

这题的关键无非就两个：

1. 如何管理好窗口
2. 如何计算窗口内题目所求的结果

由于我们需要的是一个固定的窗口大小，而且重点在于计算窗口内元素的出现次数

所以我们可以简单的用一次遍历来做这件事情，然后用一个对象 map 来计算在窗口内各个元素的出现频率

具体来说，遍历过程有三种情况需要处理：

1. 遍历一个新元素时：map[nums[i]]++ 将该元素出现频率加一
2. 如果当前指针 i >= k：map[nums[i-k]]-- 我们需要把脱离我们当前窗口范围的元素频率减回来
3. 如果当前指针 i >= k-1：此时需要根据窗口内元素计算出题目所需的结果（排序、加总）

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findXSum = function (nums, k, x) {
    // {value: occurrence}
    const map = {}
    const res = []

    for (let i = 0; i < nums.length; i++) {
        map[nums[i]] = (map[nums[i]] || 0) + 1
        if (i >= k) {
            // remove the previous data since it is no longer in the subArr
            map[nums[i - k]]--
        }
        if (i >= k - 1) {
            // [[value, occurrence]]
            const dataArr = Object.entries(map).sort((a, b) => {
                if (a[1] === b[1]) {
                    return b[0] - a[0]
                }
                return b[1] - a[1]
            })
            let sum = 0
            for (j = 0; j < Math.min(dataArr.length, x); j++) {
                sum += dataArr[j][0] * dataArr[j][1]
            }
            res.push(sum)
        }
    }
    return res
};