JZX轻语：简
LeetCode 1010 - 总持续时间可被60整除的歌曲
发表于2024年06月02日
该题目本质是统计数对(a, b)的个数，其中(a + b) % 60 == 0。由于(a + b) % 60 == 0等价于(a % 60 + b % 60) % 60 == 0，我们可以使用一个哈希表来存储前面已处理的数字模60后结果的计数，然后遍历元素b，累加哈希表中(60 - b % 60) % 60的计数即可。也可以先计数后，再遍历哈希表中的1-29的数字，累加count[i] * count[60 - i]，而对于i为1或者30的情况，则使用组合公式C(i, 2) = count[i] * (count[i] - 1) // 2来计算。
from collections import defaultdict
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
# (a + b) % 60 == a % 60 + b % 60
# for 150, 150 % 60 = 30, 我们需要找到%60后为20的数字, 仅需要存储余数为20的数字计数即可, 无需对所有的数字进行计数
mod_cnt = [0] * 60 # 存储的是 时间%60 的计数
ans = 0
for duration in time:
duration %= 60
ans += mod_cnt[(60 - duration) % 60]
mod_cnt[duration] += 1
return ans官解中，先计数后计算结果的做法：
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
cnt = [0] * 60
for t in time:
cnt[t % 60] += 1
res = 0
for i in range(1, 30):
res += cnt[i] * cnt[60 - i]
res += cnt[0] * (cnt[0] - 1) // 2 + cnt[30] * (cnt[30] - 1) // 2
return res