1010. 总持续时间可被 60 整除的歌曲
题目描述
输入数组 time，time[i] 是第 i 首歌的时长，单位为秒。
统计满足 i < j 且 (time[i] + time[j]) % 60 == 0 的下标对 (i, j) 的个数，返回这个数。
示例 1
输入：time = [30,20,150,100,40] 输出：3
解释：满足条件的是 30+150、20+100、20+40 这三对。
示例 2
输入：time = [60,60,60] 输出：3
解释：任意两首相加都是 120，三首歌两两配对共 3 对。
数据范围
1 <= time.length <= 6 * 10^41 <= time[i] <= 500
解题思路
两数之和能被 60 整除，只看它们除以 60 的余数：余数 r 需要配余数 (60 - r) % 60。用长度 60 的计数数组当哈希表，从左到右扫描：每首歌先把前面配对余数的个数加到答案，再把自己的余数计数加一。和“两数之和”一样，只是把“等于”换成了“同余”。
为什么正确
处理到第 j 首歌前，cnt[r] 是前 j 首中余数为 r 的歌曲数，ans 是两首都在前 j 首中的合法对数。
复杂度分析
时间 O(n)，空间 O(60) = O(1)。
易错点
余数为 0 的歌曲要和余数 0 配对，直接写 60 - r 会得到下标 60 越界，所以要再模 60。余数 30 与自己配对，必须先累加再计数，否则一首歌会和自己组成一对。答案可达 n^2/2 约 1.8×10^9，C++/Java 里用 64 位累加更稳妥。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
cnt = [0] * 60
ans = 0
for t in time:
r = t % 60
ans += cnt[(60 - r) % 60]
cnt[r] += 1
return ansclass Solution {
public int numPairsDivisibleBy60(int[] time) {
long[] cnt = new long[60];
long ans = 0;
for (int t : time) {
int r = t % 60;
ans += cnt[(60 - r) % 60];
cnt[r]++;
}
return (int) ans;
}
}class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
vector<long long> cnt(60, 0);
long long ans = 0;
for (int t : time) {
int r = t % 60;
ans += cnt[(60 - r) % 60];
cnt[r]++;
}
return (int)ans;
}
};func numPairsDivisibleBy60(time []int) int {
cnt := make([]int, 60)
ans := 0
for _, t := range time {
r := t % 60
ans += cnt[(60-r)%60]
cnt[r]++
}
return ans
}var numPairsDivisibleBy60 = function(time) {
const cnt = new Array(60).fill(0);
let ans = 0;
for (const t of time) {
const r = t % 60;
ans += cnt[(60 - r) % 60];
cnt[r]++;
}
return ans;
};function numPairsDivisibleBy60(time: number[]): number {
const cnt: number[] = new Array(60).fill(0);
let ans = 0;
for (const t of time) {
const r = t % 60;
ans += cnt[(60 - r) % 60];
cnt[r]++;
}
return ans;
}