Skip to content

Latest commit

 

History

History
145 lines (118 loc) · 5.71 KB

2491.md

File metadata and controls

145 lines (118 loc) · 5.71 KB
title description keywords
2491. 划分技能点相等的团队
LeetCode 2491. 划分技能点相等的团队题解，Divide Players Into Teams of Equal Skill，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
2491. 划分技能点相等的团队
划分技能点相等的团队
Divide Players Into Teams of Equal Skill
解题思路
数组
哈希表
双指针
排序

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

🟠 Medium  🔖  数组 哈希表 双指针 排序  🔗 力扣 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+ 🟠 🀄️ 🔗