Description
In a list of songs, the i-th song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.
在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i < j 且有 (time[i] + time[j]) % 60 == 0。
题目链接：https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
Difficulty: easy
Example 1:
Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Note:
- 1 <= time.length <= 60000
- 1 <= time[i] <= 500
分析
- 若遍历两边计算两个两个数的和是否可以被60整除，时间复杂度为 $O(N^2)$ ，时间会超限；
- 用字典存储每个时间数字对60的余数；
- 遍历字典，若key等于0，则只能与同样是0的成对，key为30同理，组合数是从D[d]中选两个的可能组合数；
- 其他情况，则要寻找与key值相加等于的60的组合，组合数是两边可能情况的乘积；
- 同时避免重复，只对key小于等于30的数字进行操作；
- 时间复杂度为 $O(NlogN)$ ,字典的查找时间复杂度是$O(logN)$。
参考代码
class Solution(object):
def numPairsDivisibleBy60(self, time):
import collections
D=collections.defaultdict(int)
for t in time:
D[t%60]+=1
S=0
for d in D:
if(d>30):
continue
if(d==0 or d==30):
S+=(D[d]*(D[d]-1)//2)
else:
if(60-d in D):
S+=(D[d]*D[60-d])
return S