How do I divide the players into teams with equal skill levels?

You should sort the skill array and then use a two-pointer technique to pair the smallest and largest values. Check if the sum of each team is equal before calculating the chemistry.

What happens if it's impossible to form equal skill teams?

If no valid way to divide players into equal skill teams exists, return -1.

What is the most efficient way to solve the Divide Players Into Teams of Equal Skill problem?

The most efficient solution involves sorting the array and using a two-pointer approach to ensure teams have equal skill levels.

Why is sorting important for this problem?

Sorting ensures that you can pair players with complementary skill levels, making it easier to balance the total skill of each team.

What if the chemistry of a team isn't calculated correctly?

The chemistry is calculated by multiplying the skills of the two players in the pair. Ensure you are multiplying, not adding the skills.

#2491

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

划分技能点相等的团队

给你一个正整数数组 skill ，数组长度为偶数 n ，其中 skill[i] 表示第 i 个玩家的技能点。将所有玩家分成 n / 2 个 2 人团队，使每一个团队的技能点之和相等。团队的化学反应等于团队中玩家的技能点乘积。返回所有团队的化学反应之和，如果无法使每个团队的技能点…

数组哈希表双指针排序

题目描述

给你一个正整数数组 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 <= 10⁵
skill.length 是偶数
1 <= skill[i] <= 1000

lightbulb

解题思路

方法一：排序

要使得所有 $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

13

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate correctly identifies that sorting is key to pairing players for equal skill teams.
question_mark
The candidate applies a two-pointer technique effectively to match players into teams.
question_mark
The candidate should mention checking for equal skill sums in all pairs before calculating chemistries.

warning

常见陷阱

外企场景

error
Forgetting to sort the skill array before pairing, which would result in invalid teams.
error
Not checking if all teams have the same total skill level before calculating chemistry.
error
Mistaking the chemistry calculation (multiplying skills) as just adding the skills.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there are constraints on the maximum team size?
arrow_right_alt
How would the solution change if skill[i] could be zero or negative?
arrow_right_alt
What if the problem required calculating chemistry for an odd number of players?

help

常见问题

外企场景

继续练习

#2465 不同的平均值数目 #2441 与对应负数同时存在的最大正整数 #2122 还原原数组