题目描述
给你一个正整数数组 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 <= 105
skill.length
是偶数
1 <= skill[i] <= 1000
解法
方法一:排序
要使得所有 $2$ 人团队的技能点相等,最小值一定需要跟最大值匹配。因此,我们将数组 skill
排序,然后用双指针 $i$ 和 $j$ 分别指向数组的首位,两两匹配,判断其和是否均为同一个数。
若不是,说明技能点无法相等,直接返回 $-1$,否则,将化学反应累加到答案中。
遍历结束,返回答案即可。
时间复杂度 $O(n \times \log n)$,空间复杂度 $O(\log n)$。其中 $n$ 是数组 skill
的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def dividePlayers(self, skill: List[int]) -> int:
skill.sort()
t = skill[0] + skill[-1]
i, j = 0, len(skill) - 1
ans = 0
while i < j:
if skill[i] + skill[j] != t:
return -1
ans += skill[i] * skill[j]
i, j = i + 1, j - 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public long dividePlayers(int[] skill) {
Arrays.sort(skill);
int n = skill.length;
int t = skill[0] + skill[n - 1];
long ans = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
if (skill[i] + skill[j] != t) {
return -1;
}
ans += (long) skill[i] * skill[j];
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution {
public:
long long dividePlayers(vector<int>& skill) {
sort(skill.begin(), skill.end());
int n = skill.size();
int t = skill[0] + skill[n - 1];
long long ans = 0;
for (int i = 0, j = n - 1; i < j; ++i, --j) {
if (skill[i] + skill[j] != t) return -1;
ans += 1ll * skill[i] * skill[j];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12 | func dividePlayers(skill []int) (ans int64) {
sort.Ints(skill)
n := len(skill)
t := skill[0] + skill[n-1]
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
if skill[i]+skill[j] != t {
return -1
}
ans += int64(skill[i] * skill[j])
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13 | function dividePlayers(skill: number[]): number {
const n = skill.length;
skill.sort((a, b) => a - b);
const target = skill[0] + skill[n - 1];
let ans = 0;
for (let i = 0; i < n >> 1; i++) {
if (target !== skill[i] + skill[n - 1 - i]) {
return -1;
}
ans += skill[i] * skill[n - 1 - i];
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | impl Solution {
pub fn divide_players(mut skill: Vec<i32>) -> i64 {
let n = skill.len();
skill.sort();
let target = skill[0] + skill[n - 1];
let mut ans = 0;
for i in 0..n >> 1 {
if skill[i] + skill[n - 1 - i] != target {
return -1;
}
ans += (skill[i] * skill[n - 1 - i]) as i64;
}
ans
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | var dividePlayers = function (skill) {
const n = skill.length,
m = n / 2;
skill.sort((a, b) => a - b);
const sum = skill[0] + skill[n - 1];
let ans = 0;
for (let i = 0; i < m; i++) {
const x = skill[i],
y = skill[n - 1 - i];
if (x + y != sum) return -1;
ans += x * y;
}
return ans;
};
|
方法二:计数
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 是数组 skill
的长度。