1010. 总持续时间可被 60 整除的歌曲【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 计数 + 同余

1. 📝 题目描述

• leetcode

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

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

---

示例 1：

输入：time = [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：

输入：time = [60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整除。

---

提示：

• 1 <= time.length <= 6 * 10^4
• 1 <= time[i] <= 500

2. 🎯 s.1 - 计数 + 同余

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} time
 * @return {number}
 */
var numPairsDivisibleBy60 = function (time) {
  const cnt = new Array(60).fill(0)
  let res = 0
  for (const t of time) {
    const r = t % 60
    const target = (60 - r) % 60
    res += cnt[target]
    cnt[r]++
  }
  return res
}

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度
• 空间复杂度：$O(1)$，计数数组大小固定为 60

算法思路：

• 维护一个大小为 60 的计数数组 cnt，记录各余数出现的次数
• 遍历每首歌曲，计算其余数 r = t % 60
• 需要配对的余数为 (60 - r) % 60，累加已记录的该余数的数量
• 然后将当前余数加入计数数组