Medium

题目描述

给你一个正整数数组 skill，数组长度为 n 且 n 是偶数，其中 skill[i] 是第 i 个玩家的技能点数。

将玩家分成 n / 2 个队伍，每个队伍由 2 个玩家组成，使得每个队伍的技能点数总和相等。

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

返回所有队伍化学反应的总和，如果无法将玩家分成技能点数总和相等的队伍，则返回 -1。

示例 1：

输入：skill = [3,2,5,1,3,4]
输出：22
解释：
将玩家分成以下队伍：(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 <= skill.length <= 10^5
  • skill.length 是偶数
  • 1 <= skill[i] <= 1000

解题思路

这道题的关键在于理解要将玩家分成技能总和相等的队伍，并求化学反应（技能乘积）的总和。

首先分析问题性质：如果所有队伍的技能总和都相等，设这个总和为 target，那么 target = 总技能数 / 队伍数。由于每个队伍有2个人，队伍数为 n/2，所以 target = sum(skill) / (n/2) = 2 * sum(skill) / n。

有两种主要解法：

解法一：排序 + 双指针（推荐） 将数组排序后，使用双指针从两端向中间遍历。最小值和最大值配对，如果它们的和等于目标值，继续下一对；否则返回-1。这种贪心策略是最优的，因为如果最小值不能和最大值配对，就不可能和其他值配对成功。

解法二：哈希表计数 先计算目标值，然后对每个技能值，查找是否存在配对值（target - skill[i]）。需要特别处理技能值等于 target/2 的情况，确保这类值的个数是偶数。

排序解法更直观且空间复杂度更低，是首选方案。

代码实现

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        sort(skill.begin(), skill.end());
        int n = skill.size();
        int target = skill[0] + skill[n - 1];
        long long chemistry = 0;
        
        for (int i = 0; i < n / 2; i++) {
            if (skill[i] + skill[n - 1 - i] != target) {
                return -1;
            }
            chemistry += (long long)skill[i] * skill[n - 1 - i];
        }
        
        return chemistry;
    }
};

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        n = len(skill)
        target = skill[0] + skill[-1]
        chemistry = 0
        
        for i in range(n // 2):
            if skill[i] + skill[n - 1 - i] != target:
                return -1
            chemistry += skill[i] * skill[n - 1 - i]
        
        return chemistry

public class Solution {
    public long DividePlayers(int[] skill) {
        Array.Sort(skill);
        int n = skill.Length;
        int target = skill[0] + skill[n - 1];
        long chemistry = 0;
        
        for (int i = 0; i < n / 2; i++) {
            if (skill[i] + skill[n - 1 - i] != target) {
                return -1;
            }
            chemistry += (long)skill[i] * skill[n - 1 - i];
        }
        
        return chemistry;
    }
}

/**
 * @param {number[]} skill
 * @return {number}
 */
var dividePlayers = function(skill) {
    skill.sort((a, b) => a - b);
    const n = skill.length;
    const target = skill[0] + skill[n - 1];
    let chemistry = 0;
    
    for (let i = 0; i < n / 2; i++) {
        if (skill[i] + skill[n - 1 - i] !== target) {
            return -1;
        }
        chemistry += skill[i] * skill[n - 1 - i];
    }
    
    return chemistry;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型排序解法哈希表解法
时间复杂度O(n log n)O(n)
空间复杂度O(1)O(n)

说明：

  • 排序解法：时间复杂度主要来自排序，空间复杂度为常数级别
  • 哈希表解法：时间复杂度为线性，但需要额外的哈希表空间存储技能值计数

相关题目