LeetCode 1010. 总持续时间可被 60 整除的歌曲
题目描述
题意分析
统计满足
i < j的歌曲下标对，使两首歌的总时长能够被60整除。总时长可以是任意60的倍数，不要求恰好等于60。歌曲按位置区分，即使时长相同也是不同元素。同一对只统计一次，一首歌不能与自己组成一对。
解法：余数计数
核心思路
[!blue]
一个数能否被
60整除只取决于它的余数。两首歌总时长的余数等于它们余数之和再对60取模，因此可以把所有时长归到0..59这60类，而不必逐对检查原时长。当前歌曲余数为
r时，需要另一首余数为(60 - r) % 60。当r = 0，需要的仍是0，所以外层取模不能省略；当r = 30，它与同类余数配对，但仍必须来自另一个位置。用
count保存此前歌曲各余数的出现次数。把当前歌曲当作一对中的右端点，历史互补余数有多少首，就新增多少对：answer += count[need]。然后才增加当前余数计数，让它参与后续歌曲的配对。每一组合法下标对都只会在较大下标被扫描时计入一次。先查询再登记也保证查到的都是更早的歌曲，不会与当前歌曲自身配对；即使同一余数出现很多次，次数累加仍会保留所有不同下标组合。
解题步骤
- 创建长度为
60的全零计数数组，答案初始化为0。- 依次读取歌曲时长，计算当前余数
remainder和互补余数need。- 将历史计数
count[need]加入答案。- 令
count[remainder]++，再继续处理下一首，最后返回总数。
代码实现
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] count = new int[60];
int answer = 0;
for (int t : time) {
int remainder = t % 60;
// 再次取模让余数 0 的互补余数仍为 0。
int need = (60 - remainder) % 60;
// 先查询历史歌曲，再记录当前歌曲，避免与自己配对。
answer += count[need];
count[remainder]++;
}
return answer;
}
}
func numPairsDivisibleBy60(time []int) int {
count := make([]int, 60)
answer := 0
for _, t := range time {
remainder := t % 60
// 再次取模让余数 0 的互补余数仍为 0。
need := (60 - remainder) % 60
// 先查询历史歌曲，再记录当前歌曲，避免与自己配对。
answer += count[need]
count[remainder]++
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，每首歌曲只处理一次。
- 空间复杂度：$O(1)$，计数数组长度固定为 60。
关键点总结
[!green]
- 同余关系把所有可能时长压缩成固定的余数类别。
- 当前歌曲固定作右端点，每个历史互补元素对应一个不同下标对。
- 先查后记同时保证不与自身配对、不重复统计。
- 题目最多
60000首歌，全部配对也只有1,799,970,000对，仍在 32 位有符号整数范围内。
易错点总结
[!yellow]
- 互补余数直接写成
60 - r，余数为零时会得到数组外的下标60。- 先增加计数再查找，会在余数
0或30时把当前歌曲与自己配对。- 用集合只记录某个余数是否出现过，会漏掉这个类别中不同歌曲对应的多组配对。
- 只接受余数之和为
60，会漏掉两首余数都为0的合法情况。- 把时长相同的歌曲去重，会改变题目按下标区分元素的计数方式。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 同样在扫描时查互补值，本题先对60取模，查找余数和为0模60的历史歌曲。 |
| 974. 和可被 K 整除的子数组 | 中等 | 同样利用余数消除大数值，本题两元素余数相加，原题两个前缀余数相减。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！