1010.Pairs of Songs With Total Durations Divisible by 60(总持续时间可被 60 整除的歌曲)

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
-------------本文结束你这么美,还坚持读完了-------------