在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0 。
题目链接：https://leetcode.cn/problems/pairs-of-songs-with-total-durations-divisible-by-60/
# 解题思路
- 使用 hash 计数表记录每个数出现的次数
- 从小到大枚举每个
i，则j = 60 * n - (60 - i % 60)，接着枚举n即可；需要注意的是，为了避免重复计算，只需记录j>=i时满足条件的数对。
- 若
j == i，则 ：ans += cntMap[i] * (cntMap[i] - 1) / 2 - 若
j > i，则：ans += cntMap[i] * cntMap[j]
注意 int 溢出问题
# 提交结果
# 代码
class Solution { | |
public int numPairsDivisibleBy60(int[] time) { | |
final int M = 500; | |
int[] cntMap = new int[M + 1]; | |
for (int t : time) ++cntMap[t]; | |
long ans = 0; | |
for (int i = 1; i <= M; ++i) { | |
if (cntMap[i] < 1) continue; | |
for (int j = 60 - (i % 60); j <= M; j += 60) { | |
if (j < i || cntMap[j] < 1) continue; | |
else if (j == i) ans += (long) cntMap[i] * (cntMap[i] - 1) / 2; | |
else ans += (long) cntMap[i] * cntMap[j]; | |
} | |
} | |
return (int) ans; | |
} | |
} |
