LeetCode 2491「划分技能点相等的队伍」解法详解：排序双指针与哈希计数（第 322 场周赛 B 题）

科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本篇以 codeforces-go 仓库中 第 322 场周赛 B 题题解文档 为骨架完整讲解 LeetCode 2491「Divide Players Into Teams of Equal Skill」的两种标准解法基于最小配最大贪心观察的排序法以及基于总和推导目标技能和的哈希表计数法。文章同时结合仓库内的 Go 实现与基于文本文件的自动化测试框架帮助你既掌握该题的推导思路与复杂度分析也能在本地仓库中直接运行验证。题目要点与两种解法总览题目的核心诉求是给定长度为偶数 n 的整数数组skill将所有人两两分组要求每组两人的技能点之和相等并最大化实际为唯一可计算的所有队伍技能点乘积之和若无法做到两两分组返回 -1。题解给出了两条截然不同的思路它们的结论一致、互相印证维度方法一排序方法二哈希表核心思想最小的一定与最大匹配排序后模拟配对由总和推导出目标技能和 s检查计数对称性时间复杂度O(n log n)O(n)空间复杂度O(1)忽略排序栈空间O(n)适用场景直觉直观、代码最短无需排序线性的更优解方法一排序——最小配最大的贪心配对核心观察与正确性题解给出的关键断言是如果最小的不和最大的匹配那么最大的只能和一个比最小数更大的数匹配就会导致技能点之和不相等。反证思路很直接设最小数为 x最大数为 y目标配对和为 s x y。若 y 与某个 zz 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 ansfunc 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 xy ! sum { return -1 } ans int64(x * y) } return }实现细节说明以排序后首尾元素之和作为全局目标值ssum此后每一对的x y都必须严格等于它否则立即返回 -1循环执行 n/2 次每次累加x * y。Go 版本中返回值声明为ans int64在累加时显式做int64(x * y)类型转换避免溢出与类型不匹配排序在 Go 中直接使用标准库sort.IntsPython 中使用列表内置的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 // 2func 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 0Go或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 中每两行构成一组用例一行输入、一行期望输出共三组输入skill期望输出推导过程[3,2,5,1,3,4]22total18m3s6配对 (3,3)、(2,4)、(5,1)乘积和 98522[3,4]12total7m1s7唯一配对乘积 12[1,1,2,3]-1total7 不是 m2 的倍数直接返回 -1从 leetcode.go 的源码可以看出该测试框架的工作原理它读取文本文件按fNumIn fNumOut即函数入参个数加返回值个数切分用例行再反射调用目标函数逐例比对输出。targetCaseNum 0表示跑全部用例若改为-1则不实际运行、仅用于生成测试数据等调试场景。这让题解代码的本地验证变得非常轻量go test ./leetcode/weekly/322/b/即可一键回归。小结这道题的价值在于同一结论的两条推导路径排序法依赖最小配最大的贪心观察实现直观、易于证明哈希表法从总量约束反推出目标技能和 s再用计数对称性做线性判定时间复杂度更优。两种方法都建立在一个共同事实上——所有队伍技能和相等意味着total必须能被队伍数整除且任意元素 x 的伙伴唯一确定为s - x。掌握这套由约束反推目标值、再验证配对可行性的思考框架对同类的分组配对类题目有直接迁移价值。题解文档leetcode/weekly/322/b/README.mdGo 实现leetcode/weekly/322/b/b.go测试入口leetcode/weekly/322/b/b_test.go测试用例数据leetcode/weekly/322/b/b.txt测试框架leetcode/testutil/leetcode.go赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解LeetCode 第 320 场周赛 T1「统计不等三元组」的排序分组与哈希对称性双解法codeforces go 题解LeetCode 第 320 场周赛 T1「统计不等三元组」的排序分组与哈希对称性双解法 本篇技术指南以 codeforces科学计算LeetCode 1748 唯一元素的和排序双指针与计数哈希表双解法详解LogicStack-LeetCodeLeetCode 1748 唯一元素的和排序双指针与计数哈希表双解法详解LogicStack LeetCode 本文是「刷穿 LeetCode」系列中 1教程文档NocoBase 无代码平台开发环境从零跑通5 分钟起本地服务避开 3 个高频坑NocoBase 无代码平台开发环境从零跑通5 分钟起本地服务避开 3 个高频坑 第一次在本地跑 yarn dev 时终端抛出一句 EADDRINUSE科学计算上一篇EverRoom技术架构全景Electron、NxCore Gateway 与 SQLite 本地优先设计的完整拆解下一篇sepia安全边界与硬性护栏解读为什么绝不编造是去AI味的第一铁律创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考