2025-09-08：选出和最大的 K 个元素。用go语言，给定两个长度均为 n 的整数数组 nums1 和 nums2，以及正整数 k。

对每个位置 i（0 ≤ i < n）进行如下计算：

• 找出所有下标 j（j ≠ i），使得 nums1[j] 的值严格小于 nums1[i]；

• 在这些符合条件的 j 对应的 nums2[j] 值中，最多挑选 k 个，使得被选值的和尽可能大；

• 将能得到的最大和记为 answer[i]。

返回长度为 n 的数组 answer，其中第 i 项为上述计算得到的最大和。

n == nums1.length == nums2.length。

1 <= n <= 100000。

1 <= nums1[i], nums2[i] <= 1000000。

1 <= k <= n。

输入：nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2。

输出：[80,30,0,80,50]。

解释：

对于 i = 0 ：满足 nums1[j] < nums1[0] 的下标为 [1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。

对于 i = 1 ：满足 nums1[j] < nums1[1] 的下标为 [2] ，只能选择这个值，结果为 30 。

对于 i = 2 ：不存在满足 nums1[j] < nums1[2] 的下标，结果为 0 。

对于 i = 3 ：满足 nums1[j] < nums1[3] 的下标为 [0, 1, 2, 4] ，选出其中值最大的两个，结果为 50 + 30 = 80 。

对于 i = 4 ：满足 nums1[j] < nums1[4] 的下标为 [1, 2] ，选出其中值最大的两个，结果为 30 + 20 = 50 。

题目来自力扣3478。

分步骤详细过程：

1. 初始化与数据结构准备：

   • 创建一个长度为 n 的结构体切片 a，每个元素是一个三元组 (x, y, i)，其中 x 是 nums1[i]，y 是 nums2[i]，i 是原始下标。
   • 使用 slices.SortFunc 对切片 a 按照 x（即 nums1 的值）进行升序排序。这样，所有元素将按照 nums1 的值从小到大排列。

2. 处理排序后的数组：

   • 初始化一个长度为 n 的 ans 数组（类型为 []int64），用于存储每个位置 i 的答案。
   • 创建一个最小堆 h（使用 container/heap 包实现），其底层是一个长度为 k 的整数切片，用于维护当前已处理的元素中最大的 k 个 nums2 值。
   • 初始化变量 s 为 0，用于记录当前堆中 k 个元素的和。

3. 遍历排序后的数组 a：

   • 对于每个索引 i（从0到n-1），取出当前三元组 t = (x, y, i)。
   • 处理重复的 x 值：如果当前元素的 x 值与上一个元素的 x 值相同（即 t.x == a[i-1].x），则直接使用上一个元素的答案（因为相同 nums1 值的元素，其符合条件的下标集合相同，但注意题目要求严格小于，所以相同值的下标不会相互包含？但这里实际上相同值的下标不会相互满足条件（因为严格小于），但代码中为了优化，直接复用了上一个相同 x 的答案？这里需要谨慎：实际上，相同 nums1 值的元素，在计算答案时，彼此之间不会满足条件（因为需要严格小于），所以它们的答案确实相同？但注意：当 x 相同时，它们都不会出现在对方的候选集合中（因为要求严格小于），但候选集合是相同的（都是所有严格小于 x 的元素）。因此，对于相同 x 的元素，其答案确实相同。所以代码直接复用上一个相同 x 的答案。
   • 如果当前 x 是新的（不与前一个相同），则设置 ans[t.i] = int64(s)，即当前堆中 k 个元素的和（但注意：这个 s 是处理到当前元素之前的所有小于当前 x 的元素中最大的 k 个 nums2 的和？实际上，由于数组按 x 升序排列，当前元素之前的元素都是 x 值小于当前元素的（因为严格升序？但可能有重复？实际上排序后相同 x 是相邻的，所以当前元素之前的元素（除了相同 x 的）都是严格小于当前 x 的）。因此，s 确实代表了所有严格小于当前 x 的元素中最大的 k 个 nums2 值的和。
   • 维护堆：
     • 如果当前索引 i < k（即还没有处理够 k 个元素），直接将 y 加入堆（通过赋值给 h.IntSlice[i]），并累加到 s。
     • 当 i == k 时，对堆进行初始化（调用 heap.Init(&h)），使其成为合法的最小堆。
     • 对于 i >= k 的情况：如果当前元素的 y 值大于堆顶（即当前堆中最小的元素），则用当前 y 替换堆顶，并更新和 s = s + y - 堆顶元素，然后调整堆（调用 heap.Fix(&h, 0)）。

4. 返回答案数组 ans：

   • 遍历结束后，ans 数组中的每个位置 i 存储了对于原始下标 i 的答案（即所有 nums1[j] < nums1[i] 的下标 j 中，最大的 k 个 nums2[j] 的和）。

总的时间复杂度和总的额外空间复杂度：

• 时间复杂度：

  • 排序：O(n log n)。
  • 遍历数组：O(n)。
  • 堆操作（初始化、插入、删除等）：每次堆操作的时间复杂度为 O(log k)，最坏情况下进行 O(n) 次堆操作（即每次都需要调整），所以堆操作总时间为 O(n log k)。
  • 总时间复杂度：O(n log n + n log k)。由于 k <= n，可以简化为 O(n log n)。

• 额外空间复杂度：

  • 结构体切片 a：O(n)。
  • 答案数组 ans：O(n)。
  • 堆：O(k)。
  • 总额外空间复杂度：O(n + k)，即 O(n)（因为 k <= n）。

因此，总的时间复杂度为 O(n log n)，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main

import (
	"container/heap"
	"fmt"
	"slices"
	"sort"
)

func findMaxSum(nums1, nums2 []int, k int) []int64 {
	n := len(nums1)
	type tuple struct{ x, y, i int }
	a := make([]tuple, n)
	for i, x := range nums1 {
		a[i] = tuple{x, nums2[i], i}
	}
	slices.SortFunc(a, func(p, q tuple) int { return p.x - q.x })

	ans := make([]int64, n)
	h := hp{make([]int, k)}
	s := 0
	for i, t := range a {
		if i > 0 && t.x == a[i-1].x {
			ans[t.i] = ans[a[i-1].i]
		} else {
			ans[t.i] = int64(s)
		}
		y := t.y
		if i < k {
			s += y
			h.IntSlice[i] = y
			continue
		}
		if i == k {
			heap.Init(&h)
		}
		if y > h.IntSlice[0] {
			s += y - h.IntSlice[0]
			h.IntSlice[0] = y
			heap.Fix(&h, 0)
		}
	}
	return ans
}

type hp struct{ sort.IntSlice }

func (hp) Push(any)     {}
func (hp) Pop() (_ any) { return }

func main() {
	nums1 := []int{4, 2, 1, 5, 3}
	nums2 := []int{10, 20, 30, 40, 50}
	k := 2
	result := findMaxSum(nums1, nums2, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import heapq
from typing import List

def findMaxSum(nums1: List[int], nums2: List[int], k: int) -> List[int]:
    n = len(nums1)
    # 创建元组列表 (nums1[i], nums2[i], i)
    a = [(x, nums2[i], i) for i, x in enumerate(nums1)]
    a.sort(key=lambda x: x[0])
    
    ans = [0] * n
    h = []  # 最小堆
    s = 0
    
    for i, (x, y, idx) in enumerate(a):
        if i > 0 and x == a[i-1][0]:
            # 如果当前nums1值与上一个相同，直接使用上一个的结果
            ans[idx] = ans[a[i-1][2]]
        else:
            ans[idx] = s
        
        if i < k:
            s += y
            heapq.heappush(h, y)
        else:
            if y > h[0]:
                # 替换堆中最小的元素
                s += y - h[0]
                heapq.heapreplace(h, y)
    
    return ans

# 测试代码
if __name__ == "__main__":
    nums1 = [4, 2, 1, 5, 3]
    nums2 = [10, 20, 30, 40, 50]
    k = 2
    result = findMaxSum(nums1, nums2, k)
    print(result)