🔗 🟡 2491. Divide Players Into Teams of Equal Skill 1323

tags: `Weekly Contest 322` `陣列(Array)` `雙指標(Two Pointers)` `排序(Sorting)` `雜湊表(Hash Table)`

題意

給定一個正整數陣列 $skill$ ，其長度 $n$ 為偶數，其中 $skill[i]$ 表示第 $i$ 個玩家的技能。將玩家分成 $n / 2$ 支隊伍，每個隊伍的大小為 $2$ ，使得每個隊伍的總技能相等。

一個隊伍的化學反應等於該隊伍中兩個玩家技能的乘積。

返回所有隊伍的化學反應的總和，或者如果無法將玩家分成使每個隊伍總技能相等的隊伍，則返回 $-1$ 。

約束條件

$n = \text{skill.length}$ 且 $n$ 為偶數
$2 \leq n \leq 10^5$
$1 \leq \text{skill[i]} \leq 1000$

思路：雙指標 + 排序 / 雜湊表

方法一：雙指標(Two Pointers) + 排序(Sorting)

若要每個隊伍的總技能相等，則對於技能最小的玩家，其配對的隊友技能值必定是最大的，反之亦然。

可以使用矛盾法證明，證明如下：

Proof

令 $L$ 為最小的技能值、 $H$ 為最大的技能值， $target$ 為每個隊伍的總技能值。

假設 $L$ 不能與 $H$ 配對，則 $L$ 只能與某個 $X$ 配對，其中 $L \leq X \leq H$ ； $H$ 只能與某個 $Y$ 配對，其中 $L \leq Y \leq H$ 。

由於 $L$ 和 $X$ 配對、 $H$ 和 $Y$ 配對，故 $L + X = H + Y = target$ 。得 $X = target - L$ 且 $Y = target - H$ 。

因為 $X \leq H$ ，故 $target - L \leq H$ ，即 $target \leq H + L$ ；
因為 $Y \geq L$ ，故 $target - H \geq L$ ，即 $target \geq H + L$ 。

因此， $target$ 必定等於 $H + L$ ，這與假設矛盾。故 $L$ 必定與 $H$ 配對。

而配對完 $L$ 和 $H$ 後，剩下的技能值陣列中，次小值 $L_1$ 也必定和次大值 $H_1$ 的配對，證明方式和上述相同。

因此，我們可以先將技能陣列排序，再使用雙指標法，一個指標指向最小的技能值，另一個指標指向最大的技能值，逐步向內收縮，檢查是否能配對成功。

令 $target = skill[0] + skill[n-1]$ ，表示每個隊伍的總技能值。對於要檢查的每一對玩家，若其技能和不等於 $target$ ，則無法使每個隊伍的總技能相等，返回 $-1$ ；否則，計算該隊伍的化學反應，並累加到答案中。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$
- 排序的時間複雜度為 $O(n \log n)$
- 雙指標遍歷的時間複雜度為 $O(n)$
空間複雜度： $\mathcal{O}(n)$ $O (n)$ 或 $\mathcal{O}(\log n)$ $O (lo g n)$ ，取決於排序演算法所需的空間複雜度。
- 在 Python 中，sort() 是基於 Timsort 的，其空間複雜度為 $\mathcal{O}(n)$
- 而在 C++ 中，sort() 是 QuickSort、HeapSort 和 Insertion Sort 的混合實現，其空間複雜度為 $\mathcal{O}(\log n)$ 。

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

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

方法二：雜湊表(Hash Table)

在方法一中我們假定每一組的技能和 $target$ 是 $L + H$ ，而實際上 $target$ 可以被計算得出。令 $s$ 為所有技能的總和， $m = \frac{n}{2}$ 為組別的數量，則 $target = \frac{s}{m}$ 。

在計算出 $target$ 後，對於技能為 $x$ 的玩家，其配對的隊友技能值必定為 $target - x$ 。因此，我們可以使用雜湊表來計數每個技能值的出現次數，並且確保可以組成符合條件的隊伍。

由於 $skill$ 中只存在整數值，故 $target$ 也必為整數。若 $target$ 不是整數，也就是 $s$ 不能被 $m$ 整除，則表示無法組成符合條件的隊伍，返回 $-1$ 。

接著，遍歷雜湊表，對於每個技能值 $k$ ，檢查是否存在 $target - k$ ，且兩者的出現次數相等。如果不相等，則無法形成隊伍，返回 $-1$ 。

最後，計算化學反應的總和。對於每個技能值 $k$ ，其貢獻為 $k * (target - k) * v$ ，其中 $v$ 是該技能值的出現次數。由於每對隊伍的計算都被計算了兩次，因此最後結果需要除以 $2$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ $O (n)$
- 計算總和的時間複雜度為 $O(n)$
- 遍歷雜湊表的時間複雜度為 $O(n)$
空間複雜度： $\mathcal{O}(n)$ $O (n)$
- 使用雜湊表來儲存每個技能值的出現次數，因此空間複雜度為 $O(n)$ 。

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        m = len(skill) // 2
        s = sum(skill)
        if s % m != 0:
            return -1
        target = s // m
        cnt = Counter(skill)
        ans = 0
        for k, v in cnt.items():
            if cnt[target - k] != v:
                return -1
            ans += k * (target - k) * v
        return ans // 2

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        int n = skill.size(), m = n / 2;
        int s = accumulate(skill.begin(), skill.end(), 0);
        if (s % m != 0) return -1;
        int target = s / m;
        unordered_map<int, int> cnt;
        for (int x : skill) cnt[x]++;
        long long ans = 0;
        for (auto [k, v] : cnt) {
            if (cnt[target - k] != v) return -1;
            ans += (long long) k * (target - k) * v;
        }
        return ans / 2;
    }
};