题目地址
https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
题目描述
在歌曲列表中，第 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 整数。
提示：
1 <= time.length <= 60000
1 <= time[i] <= 500
思路
- 暴力法, 算出所有对的和, 将其中和%60=0的对加起来. 这种办法超时.
-
(A+B) % 60 == 0 ==> (A%60 + B%60) %60 == 0, 这样我们可以将nums数组映射到一个长度为60的数组mods中, 索引就是%60后的值. 值就是%60后值为索引值的个数.
假设mods[i]= 2, mods[j] = 3, i+j=60.
这种情况下和%60的对数等于 mods[i]和mods[j]的排列组合即mods[i]*mods[j].
要注意mods[0]和mods[30]需要单独处理
mods[0]和mods[30]自身可以和另一个mods[0],mods[30]组合. 对数等于(n-1)!即(1~n-1)的等差数列求和.
题解
/**
* Created by zcdeng on 2021/2/23.
*/
public class NumPairsDivisibleBy60 {
public static void main(String[] args) {
int[] nums = {418,204,77,278,239,457,284,263,372,279,476,416,360,18};
int result = numPairsDivisibleBy60(nums);
System.out.println(result);
result = numPairsDivisibleBy60V2(nums);
System.out.println(result);
}
/**
* 执行用时：2 ms, 在所有 Java 提交中击败了99.68%的用户
* 内存消耗：44 MB , 在所有 Java 提交中击败了35.55%的用户
*/
private static int numPairsDivisibleBy60V2(int[] nums) {
int[] mods = new int[60];
for (int i=0; i<nums.length; i++) {
mods[nums[i] % 60] += 1;
}
int result = (mods[0] - 1) * mods[0] / 2;
for (int i=1,j=mods.length-1; i<j; i++,j--) {
result += mods[i] * mods[j];
}
result += (mods[30] - 1) * mods[30] / 2;
return result;
}
/**
* 超时
*/
private static int numPairsDivisibleBy60(int[] nums) {
if (nums.length < 2) {
return 0;
}
int result = 0;
for (int i=0; i<nums.length; i++) {
int num = nums[i];
for (int j=i+1; j<nums.length; j++) {
if ((num + nums[j]) % 60 == 0) {
result++;
}
}
}
return result;
}
}
