在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i 和 j 满足 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 整数。
解法一(暴力解法)
/**
* 暴力求解会超时
* @param time
* @return
*/
public static int numPairsDivisibleBy60(int[] time) {
int result = 0;
for(int i = 0;i<time.length;i++){
for(int j = i+1;j<time.length;j++){
if((time[i] + time[j]) % 60 == 0){
result++;
}
}
}
return result;
}
这个方法很容就能想到，但不好的是，时间复杂度O(N^2)，在leetcode中会超时。
解法二
第一种方法容易超时，开始思索第二种方法：这个题目是想求有多少对，就和两数之和类的题目相似，已知sum，求a+b=sum的a和b。
由"可以被60整除"得到"sum%60=0"，紧接着得到 "a%60 + b%60 = 0".
一样的，现在已经知道sum，如果再知道a，那我求出b的次数，再把a和b组合起来就可以知道有多少对。
举例：28%60=28, 88%60=28, a%60=28的次数为2; 32%60=32,92%60=32, b%60=32的次数为2,则组合起来为(28,32),(28,92),(88,32),(88,92),共有2X2=4对。
特例: 取模等于0和30的情况：
0%60=0,60%60=0,总有2*1/2=1对；
30%60=30,90%60=30,150%60=30,总有3*2/2=3对
/**
* 取余方法
* @param time
* @return
*/
public static int numPairsDivisibleBy60_mod(int[] time) {
int result = 0;
Map<Integer,Integer> map = new HashMap<>();
// 把所有数整除60的结果放入到Map中
for(int i = 0;i<time.length;i++){
map.put(time[i]%60,map.get(time[i]%60) == null ? 1 : map.get(time[i]%60) + 1);
}
// 前半段只需要遍历1到29
for(int i = 1;i<30;i++){
result += (map.get(i) == null ? 0 : map.get(i)) * (map.get(60-i) == null ? 0 : map.get(60-i));
}
// 针对取模为0的情况做处理
result += map.get(0) == null ? 0 : map.get(0) * (map.get(0)-1) / 2;
// 针对取模为30的情况做处理
result += map.get(30) == null ? 0 : map.get(30) * (map.get(30) -1) /2;
return result;
}