LeetCode #1010. Pairs of Songs With Total Durations Divisible by 60

题目

1010. Pairs of Songs With Total Durations Divisible by 60

解题方法

遍历数组构造一个字典，其中的键是time数组中每个数取60的模数，值是一个列表，存储相同模数的所有数的下标。然后初始化返回值rat，把0和30单独用公式n(n-1)/2计算配对个数。之后遍历字典中所有键，若模数mod和相对的配对数60-mod都在字典中，就计算配对个数。计算方法是遍历字典中模数mod的值中的每一位i，在内层循环中再遍历60-mod的list中每一位j，寻找满足j>i的个数，最后再加到rat中。
时间复杂度：不知道，挺慢的，3948ms beats 5.10%...
空间复杂度：O(n)

代码

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        dic = {}
        for i in range(len(time)):
            if time[i] % 60 in dic:
                dic[time[i] % 60].append(i)
            else:
                dic[time[i] % 60] = [i]
            
        rat = 0
        if 0 in dic:
            rat += len(dic[0])  * (len(dic[0]) - 1)  // 2
        if 30 in dic:
            rat += len(dic[30]) * (len(dic[30]) - 1) // 2
        
        for mod in dic.keys():
            if mod and mod != 30 and 60 - mod in dic:
                curcount = 0
                for i in dic[mod]:
                    for j in dic[60-mod]:
                        if j > i:
                            curcount += 1
                rat += curcount
        
        return rat

LeetCode #1010. Pairs of Songs With Total Durations Divisible by 60

原文：https://www.cnblogs.com/RatsCommander/p/14025426.html