X

LEETCODE 1010. Pairs of Songs With Total Durations Divisible by 60 解题思路分析

题目大意:

总持续时间可被 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-解题思路分析/
Categories: leetcode
kwantong: