LeetCode.1010-歌曲总长度可被60整除的对数

这是小川的第377次更新，第405篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第239题（顺位题号是1010）。在歌曲列表中，第i首歌曲的持续时间为[i]秒。

返回其总持续时间（以秒为单位）可被60整除的歌曲对的数量，即当

i <j

时，

(time[i] + time[j])％60 == 0

。

例如：

输入：[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

输入：[60,60,60]

说明：所有三对的总持续时间为120，可被60整除。

注意：

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

02 第一种解法

暴力解法，使用两层for循环，但是会超时。

public int numPairsDivisibleBy60(int[] time) {
    int count = 0, n = time.length;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if ((time[i]+time[j])%60 == 0) {
                count++;
            }
        }
    }
    return count;
}
           

03 第二种解法

我们需要将时间复杂度降到

O(N)

，就得重新考虑

time

中的元素值特性。

例如

[30,20,150,100,40]

，其中30和150可以配对，20和100可以配对，20和40可以配对，这三对数之和都可以被60整除，那我们可以事先就将这些数简化一步，对60取余，得到

[30,20,30,40,40]

，新的数范围是

[0,59]

，那么只要后面出现的数能在前面找到一个数，两者互补（即两者之和等于60的倍数），即

60-temp = temp2;

temp2

在

temp

的后面出现，变成伪代码就是

60-time[i]%60

但是换到另外一个例子上来看，

[60,60,60]

，取余后变成了

[0,0,0]

，再用60去减，发现没有可以配对的数，那我们就再取余一次，即

(60-time[i]%60)%60

，这样就可以处理那些本身是60的倍数的数。

思路：先对

time

中的数用60进行取余运算，使用一个

HashMap

，

key

为新数组的元素值，

value

为出现次数，遍历新数组中的元素

num

，找到

(60-num)%60

HashMap

中的

value

值，进行累加，最后输出。

public int numPairsDivisibleBy602(int[] time) {
    for (int i=0; i<time.length; i++) {
        time[i] %= 60;
    }
    int count = 0;
    Map<Integer, Integer> map = new HashMap<Integer,Integer>();
    for (int num : time) {
        count += map.getOrDefault((60-num)%60, 0);
        map.put(num, map.getOrDefault(num, 0)+1);
    }
    return count;
}
           

04 第三种解法

思路和第二种解法一样，将

HashMap

换成

int

数组。

public int numPairsDivisibleBy603(int[] time) {
    int[] count = new int[60];
    int result = 0;
    for (int num : time) {
        result += count[(60-num%60)%60];
        count[num%60]++;
    }
    return result;
}
           

05 小结

算法专题目前已连续日更超过七个月，算法题文章245+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，好看、留言、转发就是对我最大的回报和支持！