每日一题：总持续时间可被 60 整除的歌曲 - 刷题题解

在歌曲列表中，第 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 时满足条件的数对。

注意 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;
	}
	}