题目描述#

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。

思路#

这道题的核心思想是利用余数配对：

1. 两个数之和能被 60 整除，等价于它们对 60 取余后的和能被 60 整除
2. 对于余数 r，需要找到余数为 (60 - r) % 60 的数与之配对
3. 特别注意：
   • 余数为 0 时，需要找另一个余数为 0 的数
   • 余数为 30 时，需要找另一个余数为 30 的数
   • 使用 (60 - r) % 60 可以统一处理这两种特殊情况

算法步骤：

1. 创建长度为 60 的数组 cnt，用于记录每个余数出现的次数
2. 遍历每首歌曲的时间：
   • 计算当前时间对 60 的余数 r
   • 查找能与 r 配对的余数 (60 - r) % 60 已经出现的次数，加到答案中
   • 将当前余数 r 的计数加一

时间复杂度：O(n)，只需遍历一次数组 空间复杂度：O(1)，数组大小固定为 60

代码#

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        long ans = 0L;
        for (int t : time) {
            int r = t % 60;
            // 余数为 r 时，想要和它凑成 60 的补数是 (60 - r) % 60
            ans += cnt[(60 - r) % 60];
            cnt[r]++;
        }
        return (int) ans;
    }
}