2025-05-12：计算子数组的 x-sumⅠ。用go语言，给定一个长度为 n 的整数数组 nums，以及两个整数 k 和 x

2025-05-12：计算子数组的 x-sumⅠ。用go语言，给定一个长度为 n 的整数数组 nums，以及两个整数 k 和 x。

定义数组的 x-sum 如下：

1. 1. 统计数组中各个元素的出现频率。

2. 2. 选出出现次数最多的前 x 个元素的所有出现位置。若出现次数相同，则数值较大的元素优先被选中。

3. 3. 将选中的这些元素加起来，得到 x-sum。

如果不同的元素数量少于 x，则直接返回数组所有元素的和。

请你计算数组中所有长度为 k 的连续子数组的 x-sum，返回一个长度为 n - k + 1 的数组 answer，其中 answer[i] 表示子数组 nums[i..i + k - 1] 的 x-sum。

1 <= n == nums.length <= 50。

1 <= nums[i] <= 50。

1 <= x <= k <= nums.length。

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

目来自leetcode3318。

解决步骤

1. 1.滑动窗口：我们需要遍历所有长度为k的子数组。滑动窗口的起始位置从0到n - k。

2. 2.频率统计：对于每个子数组，统计每个元素的出现频率。

3. 3.选择前x个元素：

• • 将频率和元素值组合成(频率, 元素值)的二元组。

• • 对这些二元组排序：先按频率降序，频率相同则按元素值降序。

• • 选择前x个二元组对应的元素值。

4.计算x-sum：

• • 遍历子数组，累加被选中的元素的值。

5.优化：

• • 使用红黑树（L和R）来维护频率和元素值的排序。

• •L存储前x个最高频率的元素，R存储剩余元素。

• •sumL记录L中所有元素的频率乘以元素值的和（即x-sum）。

• • 动态维护L和R的大小关系：确保L的大小为x。

1. 1.初始化：

• •L和R是两个红黑树，用于存储(频率, 元素值)的二元组。

• •sumL记录L中所有元素的频率 * 元素值的和。

• •cnt是一个哈希表，记录当前窗口中每个元素的出现频率。

2.滑动窗口：

• • 遍历数组，每次移动窗口时：

• • • 移除左边界的元素（如果窗口已满）。

  • • 添加右边界的元素。

  • • 更新cnt和红黑树。

3.维护红黑树：

• • 添加或删除元素时，根据(频率, 元素值)更新L或R。

• • 确保L的大小为x：

• • • 如果L的大小小于x，从R中移动最大的元素到L。

  • • 如果L的大小大于x，从L中移动最小的元素到R。

4.计算x-sum：

• •sumL即为当前窗口的x-sum。

• • 滑动窗口遍历：O(n)。

• • 每次窗口移动：

• • • 更新cnt：O(1)。

  • • 红黑树操作（插入、删除、查找）：O(log m)，其中m是窗口中不同元素的数量（最多50）。

  • • 维护L和R的大小：最多O(log m)操作。

• • 总时间复杂度：O(n * log m)，其中m <= 50，因此可以认为是O(n)。

• •cnt：O(m)，m是不同元素的数量（最多50）。

• •L和R：O(m)。

• • 总空间复杂度：O(m)，即O(1)（因为m最多为50）。

总时间复杂度：O(n)（因为log m是常数）。
总额外空间复杂度：O(1)（因为m是常数）。

Go完整代码如下：

package main import (     "cmp"     "fmt"     "github.com/emirpasic/gods/v2/trees/redblacktree" ) type pair struct{ c, x int } // 出现次数，元素值 func less(p, q pair)int {     return cmp.Or(p.c-q.c, p.x-q.x) } func findXSum(nums []int, k, x int) []int64 {     L := redblacktree.NewWith[pair, struct{}](less)     R := redblacktree.NewWith[pair, struct{}](less)     sumL := 0// L 的元素和     cnt := map[int]int{}     add := func(x int) {         p := pair{cnt[x], x}         if p.c == 0 {             return         }         if !L.Empty() && less(p, L.Left().Key) > 0 { // p 比 L 中最小的还大             sumL += p.c * p.x             L.Put(p, struct{}{})         } else {             R.Put(p, struct{}{})         }     }     del := func(x int) {         p := pair{cnt[x], x}         if p.c == 0 {             return         }         if _, ok := L.Get(p); ok {             sumL -= p.c * p.x             L.Remove(p)         } else {             R.Remove(p)         }     }     l2r := func() {         p := L.Left().Key         sumL -= p.c * p.x         L.Remove(p)         R.Put(p, struct{}{})     }     r2l := func() {         p := R.Right().Key         sumL += p.c * p.x         R.Remove(p)         L.Put(p, struct{}{})     }     ans := make([]int64, len(nums)-k+1)     for r, in := range nums {         // 添加 in         del(in)         cnt[in]++         add(in)         l := r + 1 - k         if l < 0 {             continue         }         // 维护大小         for !R.Empty() && L.Size() < x {             r2l()         }         for L.Size() > x {             l2r()         }         ans[l] = int64(sumL)         // 移除 out         out := nums[l]         del(out)         cnt[out]--         add(out)     }     return ans } func main() {     nums := []int{1, 1, 2, 2, 3, 4, 2, 3}     k := 6     x := 2     result := findXSum(nums, k, x)     fmt.Println(result) }

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展