関小君刷题记

题目大意：

总持续时间可被 60 整除的歌曲

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字  i < j 且有 (time[i] + time[j]) % 60 == 0。

示例 1：

输入：[30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整数：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60

示例 2：

输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。

---

提示：

1. 1 <= time.length <= 60000
2. 1 <= time[i] <= 500

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1010

解题思路分析：

这道题与Two Sum非常类似， Two Sum是求两数之和等于一个target的个数，而本题是求两数之和等于60倍数的个数。如果两数之和是60的倍数，那么存在两种可能：

1. 两个数分别是60的倍数。即n1%60==0 并且 n2%60==0 (比如60和120)
2. 两个数与60的余数和等于60。即 n1%60 + n2%60 = 60 (比如70和50)

有了上面的思路，我们建立一个数组count，count[i]代表余数为i的个数。然后循环遍历数组中每一个数字，查看当前数字的余数，如果余数为0，那么当前count[0]的个数就是与当前数能够组成的配对数。如果余数不为0，那么count[60-当前余数]的个数就是与当前数能够组成的配对数。之后我们将当前余数的count加一。循环完整个数组，我们也就统计出了最终的结果。

实现代码：

public int numPairsDivisibleBy60(int[] time) {
    // 统计每个余数的个数
    int[] count = new int[60];
    // 返回结果
    int res=0;
    // 循环每一个数字
    for(int t : time){
        // 如果当前数字余数为0
        if(t%60==0){
            res+=count[0];
        }else{ // 当前数字余数不为0
            res+=count[60-t%60];
        }
        count[t%60]++;
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 79.27% of Java online submissions for Pairs of Songs With Total Durations Divisible by 60.

Memory Usage: 42.4 MB, less than 64.29% of Java online submissions for Pairs of Songs With Total Durations Divisible by 60.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1010-pairs-of-songs-with-total-durations-divisible-by-60-解题思路分析/