在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。
形式上，我们希望索引的数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：
输入：[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：
输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。
提示：
1 <= time.length <= 60000
1 <= time[i] <= 500
自我解答
和 twoSum 很像，不一样的是这里的 target 有很多个，于是我尝试把它们都枚举出来。
sum_times = [60*i for i in range(1, 17)]
然后按照 twoSum 的思路进行, 时间复杂度 O(n*m)
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
sum_times = [60 * i for i in range(1, 17)]
num_pairs = 0
time_map = {time[0]: 1, }
for t in time[1:]:
for st in sum_times:
num_pairs += time_map.get(st - t, 0)
if t in time_map:
time_map[t] += 1
else:
time_map[t] = 1
return num_pairs
提交结果:执行用时：484 ms, 在所有 Python3 提交中击败了 7.13%的用户。看来还不够
题解
官方题解整体思路也是 "twoSum", 但运用了数学余数规律，避免了枚举的过程，从而让时间复杂度降低到 O(n)。
那么数学余数有什么规律呢？ 我们就拿 t % 60 为例。
若 1 <= t < 60, 则 余数 = t, 如 45 % 60 = 45, 因为 t = 45 + 60 0
若 t = 60, 余数 = 0, 因为 t = 0 + 60
若 t = 62, 余数 = 2, 因为 t = 2 + 60 1
若 t = 164, 余数 = 44, 因为 t = 44 + 60 2
若 t = 220, 余数 = 40, 因为 t = 40 + 60 3
所以不管 t 多大， 都是 余数 + 60 n, 它们有相似的部分 60 n, 而且 余数范围永远是 [0, 59]
我们再拿 t = 135 举例：
我们知道 135 % 60 = 15， 即 15 + 60 2， 那么加多少后，能整除 60 呢？
可以 15 + 45 + 60 2 = 180
也可以 15 + 45 + 60 3 = 240
也可以 15 + 45 + 60 4 = 300
....
也就是说，我们只需要加 45 + 60 * n 就行了，即 只要数对 60 取余 是 45 就行了。
所以，对于 t = 135 来说，我们可以记录下 45 这名 “通缉犯”， 后面如果遇到 t % 60 == 45 的，就说明发现通缉犯了！
和 twoSum 一样，使用哈希表来记录 "wanted", 如 wanted = {45: 1}, 表示 45 被前面 1个人 “通缉”，
当发现”通缉犯“时，表示被 1 个人成功“通缉”，成功通缉数 + 1。
如果再遇到 60 - t % 60 = 45 的，则 wanted[45] += 1, 45 被 “通缉”数 +1。
还有种特殊情况，t % 60 == 0, 这种"被通缉的"就是 0
class Solution2:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
wanted = [0] * 60
num_pairs = 0
for t in time:
div = t % 60
num_pairs += wanted[div]
wanted[div if div == 0 else 60 - div] += 1
return num_pairs
执行用时：244 ms, 在所有 Python3 提交中击败了 100.00% 的用户
内存消耗：17.2 MB, 在所有 Python3 提交中击败了 7.10% 的用户
原题链接：https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60