企业官网建设流程全解析

• 科学计算

导读

本篇以 codeforces-go 仓库中 第 322 场周赛 B 题题解文档 为骨架，完整讲解 LeetCode 2491「Divide Players Into Teams of Equal Skill」的两种标准解法：基于"最小配最大"贪心观察的排序法，以及基于总和推导目标技能和的哈希表计数法。文章同时结合仓库内的 Go 实现与基于文本文件的自动化测试框架，帮助你既掌握该题的推导思路与复杂度分析，也能在本地仓库中直接运行验证。

题目要点与两种解法总览

题目的核心诉求是：给定长度为偶数 n 的整数数组skill，将所有人两两分组，要求每组两人的技能点之和相等，并最大化（实际为唯一可计算的）所有队伍技能点乘积之和；若无法做到两两分组，返回 -1。

题解给出了两条截然不同的思路，它们的结论一致、互相印证：

方法一：排序——最小配最大的贪心配对

核心观察与正确性

题解给出的关键断言是：如果最小的不和最大的匹配，那么最大的只能和一个比最小数更大的数匹配，就会导致技能点之和不相等。

反证思路很直接：设最小数为 x，最大数为 y，目标配对和为 s = x + y。若 y 与某个 z（z > x）配对，则 y + z > y + x = s，该队技能和必然超过目标值，从而整体无法满足"每队技能和相等"的要求。因此 x 与 y 必须绑定为一组，去掉这一组后，剩余数组的最小数与最大数之间仍然满足同样的性质，可以递归地继续配对。

排序后双指针模拟

基于上述观察，只需要将数组升序排序，然后用首尾双指针逐对匹配：

class Solution: def dividePlayers(self, skill: List[int]) -> int: skill.sort() ans, s = 0, skill[0] + skill[-1] for i in range(len(skill) // 2): x, y = skill[i], skill[-1 - i] if x + y != s: return -1 ans += x * y return ans

func dividePlayers(skill []int) (ans int64) { sort.Ints(skill) n := len(skill) sum := skill[0] + skill[n-1] for i := 0; i < n/2; i++ { x, y := skill[i], skill[n-1-i] if x+y != sum { return -1 } ans += int64(x * y) } return }

实现细节说明：

• 以排序后首尾元素之和作为全局目标值s（sum），此后每一对的x + y都必须严格等于它，否则立即返回 -1；
• 循环执行 n/2 次，每次累加x * y。Go 版本中返回值声明为ans int64，在累加时显式做int64(x * y)类型转换，避免溢出与类型不匹配；
• 排序在 Go 中直接使用标准库sort.Ints，Python 中使用列表内置的sort()。

复杂度分析

• 时间复杂度：O(n log n)，主要开销来自一次排序，其中 n 为skill的长度；
• 空间复杂度：O(1)，忽略排序所需的栈空间后只用到若干额外变量。

方法二：哈希表——由总和直接推导目标技能和

关键推导

设total为skill所有数之和，m为skill长度的一半（即队伍数）。既然每队技能和相等且为某个定值 s，则必然有：

• total必须是m的倍数，否则无法均分，直接返回 -1；
• 目标技能和s = total / m。

接下来不再关心元素的先后顺序，而是统计每个数值x的出现次数cnt[x]。为了凑成 s，值为 x 的人必须与值为s - x的人配对，因此对任意 x 都必须满足：

cnt[x] == cnt[s - x]

否则无法匹配，返回 -1。由于对每一组互补数对 (x, s-x)，配对总数为cnt[x]，贡献到答案中的乘积之和为：

cnt[x] * x * (s - x)

遍历哈希表时，x 与 s-x 会被各记录一次（即对称部分被重复计入），所以最终答案需要除以 2。

代码实现

class Solution: def dividePlayers(self, skill: List[int]) -> int: total, m = sum(skill), len(skill) // 2 if total % m: return -1 ans, s = 0, total // m cnt = Counter(skill) for x, c in cnt.items(): if c != cnt[s - x]: return -1 ans += c * x * (s - x) return ans // 2

func dividePlayers(skill []int) (ans int64) { total := 0 cnt := map[int]int{} for _, x := range skill { total += x cnt[x]++ } m := len(skill) / 2 if total%m > 0 { return -1 } s := total / m for x, c := range cnt { if c != cnt[s-x] { return -1 } ans += int64(c * x * (s - x)) } return ans / 2 }

实现要点：

• 先在同一个循环里累加total并统计cnt，时间复杂度 O(n)；
• 整除判断用total % m > 0（Go）或total % m的真值（Python）；
• 遍历哈希表时以任意顺序检查cnt[x] == cnt[s-x]，利用 map 不存在的 key 返回 0 的特性天然处理了"某值只在一边出现"的情况；
• 最后ans / 2去掉对称重复计数，Go 中ans为int64，除法仍为整数除法，结果不受影响。

复杂度分析

• 时间复杂度：O(n)，只需两次线性扫描（一次统计，一次遍历哈希表）；
• 空间复杂度：O(n)，用于存储cnt哈希表。

仓库中的实现与自动化测试验证

上述方法二正是仓库中保存的正式题解实现。对应源码位于 b.go，其内容与文档中的 Go 代码完全一致：先统计cnt与total，再以s = total / m检查计数对称性并累加乘积。

与 b.go 同目录的 b_test.go 揭示了该仓库的通用测试模式——通过 RunLeetCodeFuncWithFile 从文本文件驱动测试：

func Test_b(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, dividePlayers, "b.txt", targetCaseNum); err != nil { t.Fatal(err) } }

测试数据文件 b.txt 中每两行构成一组用例（一行输入、一行期望输出），共三组：

从 leetcode.go 的源码可以看出该测试框架的工作原理：它读取文本文件，按fNumIn + fNumOut（即函数入参个数加返回值个数）切分用例行，再反射调用目标函数逐例比对输出。targetCaseNum = 0表示跑全部用例；若改为-1则不实际运行、仅用于生成测试数据等调试场景。这让题解代码的本地验证变得非常轻量：go test ./leetcode/weekly/322/b/即可一键回归。

小结

这道题的价值在于"同一结论的两条推导路径"：排序法依赖"最小配最大"的贪心观察，实现直观、易于证明；哈希表法从总量约束反推出目标技能和 s，再用计数对称性做线性判定，时间复杂度更优。两种方法都建立在一个共同事实上——所有队伍技能和相等，意味着total必须能被队伍数整除，且任意元素 x 的伙伴唯一确定为s - x。掌握这套"由约束反推目标值、再验证配对可行性"的思考框架，对同类的分组配对类题目有直接迁移价值。

• 题解文档：leetcode/weekly/322/b/README.md
• Go 实现：leetcode/weekly/322/b/b.go
• 测试入口：leetcode/weekly/322/b/b_test.go
• 测试用例数据：leetcode/weekly/322/b/b.txt
• 测试框架：leetcode/testutil/leetcode.go

• 科学计算