这是小川的第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]
输出：3
说明：所有三对的总持续时间为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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，好看、留言、转发就是对我最大的回报和支持！
