# 1011. Pairs of Songs With Total Durations Divisible by 60

**<font color=red>难度: Easy</font>**

## 刷题内容

> 原题连接

* https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

> 内容描述

```
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.

 

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
```

## 解题方案

> 思路 1
******- 时间复杂度: O(N^2)******- 空间复杂度: O(1)******

先算出每种数字出现的次数

然后取出2个数字看即可
1. 两个数字不同
2. 两个数字相同（但是必须保证这种数字出现至少2次）

```python
class Solution:
    def numPairsDivisibleBy60(self, time):
        s = collections.Counter(time)
        uni_time = list(s.keys())
        res = 0
        for i in range(len(uni_time)): # 两个数字不同
            for j in range(i+1, len(uni_time)):
                if (uni_time[i] + uni_time[j]) % 60 == 0:
                    res += s[uni_time[i]] * s[uni_time[j]]

        for i in range(len(uni_time)): # 两个数字相同
            if (uni_time[i] + uni_time[i]) % 60 == 0:
                cnt = s[uni_time[i]]
                if s[uni_time[i]] >= 2: # 但是必须保证这种数字出现至少2次
                    res += self.permu(cnt) // (self.permu(2) * self.permu(cnt-2))
        return res
    
    def permu(self, cnt):
        res = 1
        for i in range(1, cnt+1):
            res *= i
        return res
```