2025-05-12：计算子数组的 x-sumⅠ 用go语言，给定一个长度为 n 的

摘要：统计数组中各个元素的出现频率。2. 选出出现次数最多的前 x 个元素的所有出现位置。若出现次数相同，则数值较大的元素优先被选中。3. 将选中的这些元素加起来，得到 x-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。

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

• 滑动窗口遍历：O(n)。• 每次窗口移动：• 更新 cnt：O(1)。• 红黑树操作（插入、删除、查找）：O(log m)，其中 m 是窗口中不同元素的数量（最多 50）。• 维护 L 和 R 的大小：最多 O(log m) 操作。• 总时间复杂度：O(n * log m)，其中 m package mainimport ( "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 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)}