题目

在一个歌单列表中,第i首歌有time[i]秒。

返回在这个歌单中,有多少对歌曲,他们的秒数之和能被60整数。也就是说,我们希望在数组time中索引i<j,并且(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. 1 <= time.length <= 60000
  2. 1 <= time[i] <= 500

思路

这个题目是求多少个(time[i]+time[j])%60==0,而我们知道(x+y)%60=0可以转化为x%60+y%60=60,也就是x%60 = 60-y%60。题目也就清楚了,我们只需要知道有多少对x%60=60-y%60就行了。

当然了,我们其实能发现上面的这个等式其实有一个bug,那就是,如果y=0的时候,x%60=60,而这是不可能的,因为x%60的范围是0-59,但是现在的话,这个范围是0-60,那么我们怎么让他变为0-59呢?其实很简单,也就是等式右边再余60即可,也就是x%60=(60-y%60)%60

好了,我们已经找到一个牛逼的等式了。那么接下来呢?当然是看有多少对x%60=(60-y%60)%60啦。而这个问题,而这个问题,我们可以通过遍历以下数组time即可,然后看一下(60-y%60)%60的余数在这个数组中有多少个x%60的值和其值即可。又因为我们是60为余数,因此我们可以申请一个60定长的数组用来存储以下x%60的的值。于是就有了下面的代码:

func numPairsDivisibleBy60(time []int) int {
    res := 0
    mod := make([]int, 60, 60)
    for _, v := range time {
        // 这里其实非常精妙,其实就是看他这个(60-y%60)%60对应的x%60有多少个,其实如果按照暴力算法来看的话,也就是看这货前面有几个x%60=(60-y%60)%60
        // 这里的核心是,后面的和前面的进行比对,而不是前面的数字和后面的进行比对,这里是关键
        res += mod[(60-v%60)%60]
        mod[v%60]++
    }

    return res
}

上面关键的代码写了注释,这里就不展开了。

原题目见:https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
完整代码见: https://github.com/scofieldpeng/leetcode/blob/master/numPairsDivisibleBy60/numPairsDivisibleBy60.go