2491. 划分技能点相等的团队

🟠   🔖  数组 哈希表 双指针 排序  🔗 力扣 LeetCode

题目

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.

The chemistry of a team is equal to the product of the skills of the players on that team.

Return _the sum of the chemistry of all the teams, or return _-1 if there is no way to divide the players into teams such that the total skill of each team is equal.

Example 1:

Input: skill = [3,2,5,1,3,4]

Output: 22

Explanation:

Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.

The sum of the chemistry of all the teams is: 1 _ 5 + 2 _ 4 + 3 * 3 = 5 + 8 + 9 = 22.

Example 2:

Input: skill = [3,4]

Output: 12

Explanation:

The two players form a team with a total skill of 7.

The chemistry of the team is 3 * 4 = 12.

Example 3:

Input: skill = [1,1,2,3]

Output: -1

Explanation:

There is no way to divide the players into teams such that the total skill of each team is equal.

Constraints:

• 2 <= skill.length <= 10^5
• skill.length is even.
• 1 <= skill[i] <= 1000

题目大意

给你一个正整数数组 skill ，数组长度为 偶数 n ，其中 skill[i] 表示第 i 个玩家的技能点。将所有玩家分成 n / 2 个 2 人团队，使每一个团队的技能点之和 相等 。

团队的 化学反应 等于团队中玩家的技能点 乘积 。

返回所有团队的 化学反应 之和，如果无法使每个团队的技能点之和相等，则返回 -1 。

解题思路

这道题的解题思路和 第 1 题 Two Sum 很像，可以使用哈希表来寻找配对的另一个数。

1. 首先计算数组 skill 的总和 sum，并确定数组的长度 n。
   • 如果总和 sum 不能被 n / 2 整除，那么就无法将这些技能值分成若干对使得每对的和相等，此时直接返回 -1。
2. 接着计算平均每一对技能值的和 equalSum，它等于 sum 除以 n / 2。
3. 然后遍历数组 skill。
   • 对于当前元素 skill[i]，计算与其配对的另一个技能值 another，即 equalSum - skill[i]。
   • 如果在 map 中找到了这个配对的技能值 another，说明找到了一对满足条件的技能值。
     • 将这一对技能值的乘积加到结果 res 中。
     • 如果 map 中对应 another 的值为 1，则从 map 中删除这个键值对；如果大于 1，则将对应的值减 1。
   • 如果没有找到配对的技能值，就将当前技能值 skill[i] 存入 map 中，并将其计数加 1。
4. 最后，检查 map 的大小是否为 0。
   • 如果是 0，说明所有的技能值都成功配对，返回结果 res。
   • 如果不为 0，说明存在无法配对的技能值，返回 -1。

复杂度分析

• 时间复杂度：O(n)
  • 计算总和和判断整除性的操作需要 O(n) 的时间，其中 n 是数组 skill 的长度。
  • 遍历数组 skill 的操作也需要 O(n) 的时间。
  • 在遍历过程中，对 Map 的查找、插入和删除操作可以近似看作是常数时间操作。
  • 因此，总体时间复杂度为 O(n)。
• 空间复杂度：O(n)
  • 使用了一个 Map 来存储技能值及其出现的次数，在最坏的情况下，可能需要存储 n/2 个不同的技能值，因此空间复杂度为 O(n)。

代码

/**
 * @param {number[]} skill
 * @return {number}
 */
var dividePlayers = function (skill) {
	const sum = skill.reduce((a, b) => a + b, 0),
		n = skill.length;
	if (sum % (n / 2) !== 0) return -1;
	const equalSum = sum / (n / 2);
	let map = new Map(),
		res = 0;
	for (let i = 0; i < n; i++) {
		const another = equalSum - skill[i];
		if (map.has(another)) {
			res += skill[i] * another;
			if (map.get(another) == 1) {
				map.delete(another);
			} else {
				map.set(another, map.get(another) - 1);
			}
		} else {
			map.set(skill[i], (map.get(skill[i]) || 0) + 1);
		}
	}
	return map.size == 0 ? res : -1;
};

相关题目

题号	标题	题解	标签	难度
453	最小操作次数使数组元素相等		数组 数学
1679	K 和数对的最大数目	[✓]	数组 哈希表 双指针 1+