LeetCode 1010. 总持续时间可被 60 整除的歌曲
目录
题目描述
题意分析
给一个歌曲时长数组，统计有多少个下标对
(i, j)（要求i < j）满足两首歌时长之和是 60 的整数倍。要点全在「下标对」三个字上：统计的是无序的组合而不是有序的排列，同一对不能算两次；而且是对的数量，不是把配对本身列出来，所以完全不必真的枚举出每一对，只要能算出个数就行。这就为「一边扫描一边累加」留出了空间。
「和能被 60 整除」这个条件只依赖余数：
(a + b) % 60 == 0等价于a % 60与b % 60相加是 60 或 0。也就是说，每首歌的完整时长是冗余信息，只有它对 60 的余数有用。余数只有 0 到 59 这 60 种取值，值域极小——这正是「用固定长度的计数数组代替哈希表」的信号。约束是
1 ≤ time.length ≤ 6 × 10^4，1 ≤ time[i] ≤ 500。数组规模决定了 $O(n^2)$ 的两两枚举（约 $1.8 \times 10^9$ 次）会超时，必须做到线性或近线性。答案上界是 $\binom{n}{2} \approx 1.8 \times 10^9$，超出int范围——不过本题保证答案在int内（LeetCode 的返回类型就是int），实际数据不会构造出全同余的极端输入。边界最容易踩的是余数 0 自我配对：余数为 0 的歌只能和另一首余数也为 0 的歌组合，此时「互补余数」不是
60 - 0 = 60，而是 0 本身。余数 30 是另一个自配对的情形（30 + 30 = 60），但它的互补余数按60 - 30算恰好还是 30，不需要特殊处理。
解法：余数计数
核心思路
两首歌的总时长能被 60 整除，只取决于各自除以 60 的余数。当前歌曲余数为
r时，它需要的互补余数是(60 - r) % 60。外层取模用于把r = 0的互补余数从 60 映射回 0；余数 30 则与自身互补。从左到右把当前歌曲当作配对的右端点，用长度为 60 的数组
count记录此前各余数出现的次数。当前歌曲能新增的合法配对数，正是count[(60-r)%60]。不变量：处理当前歌曲之前，
count[x]等于所有已处理歌曲中余数为x的数量，answer等于右端点已经处理完的全部合法下标对数量。 因此必须先查询并累加答案，再把当前余数写入计数表。这样每个合法对只会在处理其右端点时被统计一次，不会重复；当前元素尚未入表，也不会与自己配对。遍历结束后，所有
i < j的下标对都恰好被检查一次，答案正确。
解题步骤
- 创建长度为 60 的计数数组
count。- 对每个时长
t，计算余数r = t % 60。- 计算互补余数
need = (60 - r) % 60，将count[need]加入答案。- 执行
count[r]++，让当前歌曲参与后续配对。对
[30, 20, 150, 100, 40]，余数依次是[30, 20, 30, 40, 40]：第二个余数 30 与此前的 30 配成 1 对，两个余数 40 分别与此前的 20 配对，共得到 3 对。边界
[60, 60, 60]中余数都为 0，三次查询分别贡献0、1、2，结果为 3，正好是三首歌两两组合的数量。
代码实现
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] count = new int[60];
int answer = 0;
for (int t : time) {
int remainder = t % 60;
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
need := (60 - remainder) % 60
answer += count[need]
count[remainder]++
}
return answer
}
复杂度分析
- 时间复杂度： $O(n)$。每首歌只进行常数次取模、查询和更新。
- 空间复杂度： $O(1)$。计数数组固定为 60 个元素，与输入规模无关。
- 计数范围： 当 $n \le 60000$ 时，配对数最多为 $\binom{n}{2}=1,799,970,000$，仍小于 32 位有符号整数上限，因此 Java/Go 代码使用
int安全。
关键点总结
- 先把时长压缩为余数；原始时长不同，只要余数相同，对配对的作用就完全相同。
- 固定当前元素为右端点并查询历史计数，可天然满足
i < j，且每对只统计一次。- “先查询、后写入”是维护前缀计数不变量的关键，也避免元素与自身配对。
(60-r)%60统一处理普通余数、余数 0 和余数 30，无需额外分支。
易错点总结
- 把互补余数直接写成
60-r：[60, 60]中r = 0，访问count[60]会越界；正确互补余数是 0。- 先更新计数再查询：
[30]会把唯一的歌曲与自己配成一对，错误返回 1。- 只判断两个余数之和等于 60：
[60, 120]的余数和是 0，也应构成合法配对。- 建立完整计数后直接相乘： 余数 0 和 30 要计算组合数，其他互补余数还会被统计两次；在线“先查后写”可避免这些分支。
- 双重循环枚举下标对： 当歌曲数为 $6\times10^4$ 时需要约 $1.8\times10^9$ 次检查，会超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1. 两数之和 | 简单 | 同样是「固定右端点查左侧表」，但要返回下标而非数量，表里存的是位置不是计数 |
| 1512. 好数对的数目 | 简单 | 配对条件变成两数相等，互补量就是自身，最能凸显「先查后写」的作用 |
| 974. 和可被 K 整除的子数组 | 中等 | 统计对象从「两个元素」变成「子数组」，余数要对前缀和取，负数取模还要修正 |
| 523. 连续的子数组和 | 中等 | 同为前缀和余数，但要求子数组长度至少为 2，表里得存最早出现的下标 |
| 560. 和为 K 的子数组 | 中等 | 去掉取模、改为精确和，值域不再有界，只能用哈希表而非定长计数数组 |
| 454. 四数相加 II | 中等 | 四个数组两两分组后再配对，是「查表配对」思路的分治式扩展 |
| 1497. 检查数组对是否可以被 k 整除 | 中等 | 同样按余数配对，但要求全部元素恰好两两配完，判据变成余数计数是否对称相等 |