难度: Medium
在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：
输入：time = [30,20,150,100,40] 输出：3 解释：这三对的总持续时间可被 60 整除： (time[0] = 30, time[2] = 150): 总持续时间 180 (time[1] = 20, time[3] = 100): 总持续时间 120 (time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：
输入：time = [60,60,60] 输出：3 解释：所有三对的总持续时间都是 120，可以被 60 整除。
提示：
1 <= time.length <= 6 * 1041 <= time[i] <= 500运行时间: 36 ms
内存: 20.4 MB
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
li = range(60)
d = dict(zip(li, [0] * 60))
for i in time:
m = i % 60
d[m] += 1
ret = 0
for j in range(1, 30):
m = d[j]
n = d[60-j]
ret += m*n
ret += int(d[0]*(d[0]-1)/2)
ret += int(d[30]*(d[30]-1)/2)
return ret
题解使用了哈希表来统计每个时间模60的结果的频率。接着，对于每种模数结果，寻找与其配对的模数结果，使得两者之和为60。特别地，对于模数0和30的情况（即自身加自身能被60整除的情况），使用组合数公式计算配对方式。这种方法避免了直接的双层循环暴力检查，从而提高了效率。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
# 创建一个大小为60的字典来存储时间模60的结果的频率
li = range(60)
d = dict(zip(li, [0] * 60))
# 填充字典
for i in time:
m = i % 60
d[m] += 1
# 初始化结果变量
ret = 0
# 计算模数1到29及其与60的补数的配对数
for j in range(1, 30):
m = d[j]
n = d[60-j]
ret += m*n
# 单独计算模数0和30的配对数
ret += int(d[0]*(d[0]-1)/2)
ret += int(d[30]*(d[30]-1)/2)
# 返回结果
return ret
选择使用60个槽来存储模数结果是因为题目要求找出两首歌的总持续时间可以被60整除。通过计算每首歌持续时间对60的余数（模数），我们可以简化问题为查找两个数的模数之和是否等于60。哈希表（或字典）以余数作为键，以该余数出现的次数作为值，非常适合于快速查找和更新操作。使用60个槽正好覆盖了所有可能的余数结果（0到59），这是因为任何数除以60的余数必定在这个范围内，因此这样的数据结构和大小选择是最合适的。
在计算模数0和30的配对数时使用组合数公式是因为这两个特殊的模数与自身配对仍然能保持总和被60整除（0+0=0，30+30=60）。组合数公式 C(n, 2) = n*(n-1)/2 是用来计算从n个相同项中任选两项的组合方式的数量。这种计算方式在模数相同且至少出现两次时是正确的，因为每对组合都是一个有效配对。例如，如果某个模数出现了3次，那么这三项之间可以形成3*(3-1)/2 = 3种配对方式。
算法中对于模数1到29及其与60的补数进行配对，没有包括模数30以上的数字是因为这些情况在计算模数1到29时已经考虑过了。由于模数和其补数的和必须为60，模数1的补数是59，模数2的补数是58，依此类推。当我们考虑到模数29（其补数是31）时，已经包含了所有可能的组合情况，除了模数30（与自身配对），这种情况单独处理。因此，模数30到59的配对在前面已经被算过一次，无需重复计算。