class Solution {
public:
long long dividePlayers(vector<int>& skill) {
}
};
2491. 划分技能点相等的团队
给你一个正整数数组 skill ，数组长度为 偶数 n ，其中 skill[i] 表示第 i 个玩家的技能点。将所有玩家分成 n / 2 个 2 人团队，使每一个团队的技能点之和 相等 。
团队的 化学反应 等于团队中玩家的技能点 乘积 。
返回所有团队的 化学反应 之和，如果无法使每个团队的技能点之和相等，则返回 -1 。
示例 1：
输入：skill = [3,2,5,1,3,4] 输出：22 解释： 将玩家分成 3 个团队 (1, 5), (2, 4), (3, 3) ，每个团队的技能点之和都是 6 。 所有团队的化学反应之和是 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22 。
示例 2：
输入：skill = [3,4] 输出：12 解释： 两个玩家形成一个团队，技能点之和是 7 。 团队的化学反应是 3 * 4 = 12 。
示例 3：
输入：skill = [1,1,2,3] 输出：-1 解释： 无法将玩家分成每个团队技能点都相等的若干个 2 人团队。
提示：
2 <= skill.length <= 105skill.length 是偶数1 <= skill[i] <= 1000原站题解
python3 解法, 执行用时: 64 ms, 内存消耗: 25.2 MB, 提交时间: 2022-12-14 11:39:31
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
golang 解法, 执行用时: 64 ms, 内存消耗: 8.1 MB, 提交时间: 2022-12-14 11:38:05
// 基于哈希表
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
}
golang 解法, 执行用时: 96 ms, 内存消耗: 8.2 MB, 提交时间: 2022-12-14 11:37:06
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
}
python3 解法, 执行用时: 104 ms, 内存消耗: 25.1 MB, 提交时间: 2022-12-14 11:36:54
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
python3 解法, 执行用时: 136 ms, 内存消耗: 25.1 MB, 提交时间: 2022-12-14 11:36:10
class Solution:
def dividePlayers(self, skill: List[int]) -> int:
skill.sort()
n = len(skill)
m = skill[0] + skill[-1]
ans = skill[0] * skill[-1]
for i in range(1, n//2):
if skill[i] + skill[n - 1 - i] != m:
return -1
ans += skill[i] * skill[n-1-i]
return ans