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

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

定义数组的 x-sum 如下：

1. 统计数组中各个元素的出现频率。
2. 选出出现次数最多的前 x 个元素的所有出现位置。若出现次数相同，则数值较大的元素优先被选中。
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.滑动窗口：我们需要遍历所有长度为k的子数组。滑动窗口的起始位置从0到n - k。
2.频率统计：对于每个子数组，统计每个元素的出现频率。
3.选择前x个元素：

• 将频率和元素值组合成(频率, 元素值)的二元组。
• 对这些二元组排序：先按频率降序，频率相同则按元素值降序。
• 选择前x个二元组对应的元素值。

4.计算x-sum：

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

5.优化：

• 使用红黑树（L和R）来维护频率和元素值的排序。
•L存储前x个最高频率的元素，R存储剩余元素。
•sumL记录L中所有元素的频率乘以元素值的和（即x-sum）。
• 动态维护L和R的大小关系：确保L的大小为x。

详细过程

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) }