1010. Pairs of Songs With Total Durations Divisible by 60
本文共 852 字，大约阅读时间需要 2 分钟。
为了解决这个问题，我们需要找到满足特定条件的歌曲对，使得它们的总时长能被60整除。我们可以通过对每个歌曲的时长取模60来简化问题，并使用哈希表来记录余数出现的次数，从而高效地计算满足条件的对数。
方法思路
问题分析：我们需要找到两个索引i和j，使得i < j且time[i] + time[j]能被60整除。通过对每个元素取模60，我们可以将问题转化为寻找余数对，使得它们的和模60等于0。 哈希表记录：使用哈希表记录每个余数出现的次数。这样，在处理每个余数时，我们可以快速查找所需的余数对。 处理余数对：对于每个余数r，计算需要的余数s = (60 - r) % 60。如果r是0，直接使用当前余数记录的次数；否则，查找s的记录次数，并累加到结果中。 特殊情况处理：当余数为0时，直接累加当前余数的次数，处理所有可能的对数。 解决代码
from collections import defaultdictdef numPairsDivisibleBy60(time): record = defaultdict(int) count = 0 for t in time: r = t % 60 if r == 0: count += record[r] else: s = 60 - r count += record.get(s, 0) record[r] += 1 return count
代码解释
初始化：使用defaultdict来记录余数出现的次数。 遍历每个时间：对于每个时间t，计算其对60取模的结果r。 处理余数对： - 如果r为0，直接累加当前余数的次数。
- 否则，计算所需的余数s，并查找s的次数，累加到结果中。
更新记录：将当前余数r的次数增加1，供下一步处理使用。 这种方法的时间复杂度为O(n)，处理每个元素只需常数时间，非常高效。
转载地址：http://sxqo.baihongyu.com/