哈希表

哈希表（Hash Table）是一种使用哈希函数将键（key）映射到值（value）的数据结构。其基本思想是将数据存储在一个数组中，通过计算键的哈希值来确定其在数组中的索引位置。哈希表具有以下特点：

• 快速查找：平均情况下，哈希表的查找时间复杂度为 O(1)，即常数时间。
• 快速插入与删除：在理想情况下，插入和删除操作的时间复杂度也是 O(1)。
• 碰撞处理：由于不同的键可能会计算出相同的哈希值（称为碰撞），通常会通过链地址法（链表或树）或开放地址法等方式来处理碰撞。

哈希表常用于实现字典、集合等数据结构。

排序

排序是将一组数据按照特定的顺序（通常是升序或降序）进行排列的过程。常见的排序算法有：

• 冒泡排序：通过重复交换相邻的元素，把大的元素逐渐“冒泡”到数组的一端。
• 选择排序：每次从未排序的数组中选出最小的元素，放到已排序部分的末尾。
• 插入排序：将元素逐个插入到已排序序列中的合适位置。
• 快速排序：使用分治法，将数组分成两部分，使得一部分的所有元素小于另一部分的所有元素，然后递归排序这两部分。
• 归并排序：同样使用分治法，将数组分成两部分，分别排序后再合并。

排序算法的时间复杂度各不相同，简单排序算法通常是 O(n^2)，而高效的排序算法如快速排序和归并排序的平均时间复杂度为 O(n log n)。

数组

数组（Array）是一种线性数据结构，用于按顺序存储多个相同类型的数据。数组的特点包括：

• 固定大小：数组的大小在创建时确定，通常不能动态调整。
• 随机访问：可以通过索引快速访问数组中的元素，时间复杂度为 O(1)。
• 连续内存：数组的元素在内存中是连续存储的，这使得数组在空间上更加紧凑。

数组适用于需要快速访问和修改元素的场景，但由于其固定大小和在插入和删除时可能需要移动元素的特性，数组并不是所有情况下的最佳选择。

ok，话不多说，直接看题：

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

题目：

给你一个正整数数组 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 人团队。

分析问题：

思路1：

        这里可以先根据数组的长度来获得平均和key值，然后对skill数组进行一个排序，那么如果想等于key值的话，只能让最大值+最小值，如果有一个不符合题意则直接return -1。将符合题意的两个值的乘积全部加起来，最后return 就是结果。思路很简单。但是时间复杂度相比之下略高。

思路2：

        首先计算出所有技能值的总和以及每个团队理想的技能值总和。然后通过遍历技能值及其出现次数，判断能否将技能值两两分组，使得每组的技能值总和都等于理想值，同时计算出所有分组产生的化学效能总和。如果在过程中出现无法满足分组条件的情况，就返回 -1 ，否则返回计算得到的化学效能总和。

代码实现：

思路1代码实现：

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

​

思路2代码实现： 

​

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        # 计算所有技能值的总和
        s = sum(skill)
        # 计算团队数量（因为要两两分组，所以团队数量是技能值个数的一半）
        n = len(skill) // 2
        # 如果总和不能被团队数量整除，说明无法平均分配，返回 -1
        if s % n:
            return -1
        # 计算每个团队的理想技能值总和
        t = s // n
        # 初始化最终的化学效能总和为 0
        ans = 0
        # 使用 Counter 统计每个技能值出现的次数
        cnt = Counter(skill)
        # 遍历统计得到的技能值
        for k in list(cnt.keys()):
            # 如果当前技能值 k 与理想值 t - k 相等
            if k == t - k:
                # 如果该技能值的出现次数为奇数，无法两两配对，返回 -1
                if cnt[k] % 2:
                    return -1
                # 计算该技能值两两配对产生的化学效能，并累加到总和中
                ans += k*k*cnt[k]//2
            else:
                # 如果当前技能值 k 和 t - k 的出现次数相等
                if cnt[k] == cnt[t - k]:
                    # 计算它们配对产生的化学效能，并累加到总和中
                    ans += k*(t - k)*cnt[k]
                    # 将这两个技能值的出现次数置为 0，表示已经处理完
                    cnt[k] = cnt[t - k] = 0
                else:
                    # 如果出现次数不相等，无法满足两两配对的条件，返回 -1
                    return -1
        # 返回最终的化学效能总和
        return ans

​​

​

总结：

         两种方法，思路1较容易想出来但是复杂度略高。思路2相比于思路1可能没那么容易想出来，但是复杂度还是很优的。下面对思路2进行代码详解：

思路2代码详解：

        首先，通过计算技能值的总和以及团队数量，来判断是否能够平均分配技能值。如果不能整除，说明无法实现平均分组，直接返回 -1 。

        然后，创建一个计数器 cnt 来统计每个技能值出现的次数。

        接下来，遍历所有的技能值。对于每个技能值 k ，分两种情况处理：

1. 如果 k 与理想差值 t - k 相等，需要检查其出现次数是否为偶数，因为只有偶数次才能两两配对。如果是偶数次，计算 k 两两配对产生的化学效能并累加到结果中。
2. 如果 k 与理想差值 t - k 不相等，那么需要检查 k 和 t - k 的出现次数是否相等，如果相等则计算它们配对产生的化学效能，否则说明无法满足两两配对的条件，直接返回 -1 。

        最后，如果整个遍历过程都没有出现无法配对的情况，就返回计算得到的化学效能总和。

考点：

1. 数学计算，如求和、整除判断。
2. 数据结构 Counter 的使用。
3. 条件判断和逻辑处理。

收获：

1. 学习如何有效地处理整数列表的分组问题，包括总和计算、平均分配判断等。
2. 掌握使用 Counter 来高效统计元素出现次数的方法。
3. 提升通过遍历和条件判断来解决复杂逻辑问题的能力。
4. 了解如何在代码中确保数据满足特定条件，不满足时进行错误处理返回特定值。

“无聊的并不是时间，而是平庸无奇的我。”——《樱花庄的宠物女孩》