LeetCode 1010中等哈希/取模
总持续时间可被 60 整除的歌曲 图解题解
这道题到底在问什么
给定时长数组 time，统计下标对 (i, j)（i < j）满足 time[i] + time[j] 能被 60 整除的对数。
- 输入
- time=[30,20,150,100,40]
- 输出
- 3 （20+100、20+40、150+30）
最优解：一步一步想明白
- 3记住「余数 r 找互补 c=(60−r)%60:先加前面 c 的个数，再把自己 r 记进表」，下面每帧都在套它。
- 4开局计数表是空的。我们从左到右一首一首处理：先拿当前余数去表里找「互补余数」配对，再把当前余数登记进表。
- 5处理第 0 首歌（时长 30）。它对 60 的余数是 30，那么能和它凑成整 60 的「另一半」余数就是 (60 − 30) % 60 = 30。
- 6表里还没有余数为 30 的歌，这首暂时配不上谁，答案不变，仍是 0。
- 7把当前这首的余数 30 记进表（count[30] = 1），后面再来余数为 30 的歌时就能配上它。继续下一首。
- 8处理第 1 首歌（时长 20）。它对 60 的余数是 20，那么能和它凑成整 60 的「另一半」余数就是 (60 − 20) % 60 = 40。
- 9表里还没有余数为 40 的歌，这首暂时配不上谁，答案不变，仍是 0。
- 10把当前这首的余数 20 记进表（count[20] = 1），后面再来余数为 40 的歌时就能配上它。继续下一首。
- 11处理第 2 首歌（时长 150）。它对 60 的余数是 30，那么能和它凑成整 60 的「另一半」余数就是 (60 − 30) % 60 = 30。
- 12表里余数为 30 的歌有 1 首（高亮行），它们各能和当前这首配成一对，答案加 1，累计 1。
- 13把当前这首的余数 30 记进表（count[30] = 2），后面再来余数为 30 的歌时就能配上它。继续下一首。
- 14处理第 3 首歌（时长 100）。它对 60 的余数是 40，那么能和它凑成整 60 的「另一半」余数就是 (60 − 40) % 60 = 20。
- 15表里余数为 20 的歌有 1 首（高亮行），它们各能和当前这首配成一对，答案加 1，累计 2。
- 16把当前这首的余数 40 记进表（count[40] = 1），后面再来余数为 20 的歌时就能配上它。继续下一首。
- 17处理第 4 首歌（时长 40）。它对 60 的余数是 40，那么能和它凑成整 60 的「另一半」余数就是 (60 − 40) % 60 = 20。
- 18表里余数为 20 的歌有 1 首（高亮行），它们各能和当前这首配成一对，答案加 1，累计 3。
- 19把当前这首的余数 40 记进表（count[40] = 2），后面再来余数为 20 的歌时就能配上它。继续下一首。
- 20处理第 5 首歌（时长 60）。它对 60 的余数是 0，那么能和它凑成整 60 的「另一半」余数就是 (60 − 0) % 60 = 0。
- 21表里还没有余数为 0 的歌，这首暂时配不上谁，答案不变，仍是 3。
- 22把当前这首的余数 0 记进表（count[0] = 1），后面再来余数为 0 的歌时就能配上它。继续下一首。
- 23处理第 6 首歌（时长 90）。它对 60 的余数是 30，那么能和它凑成整 60 的「另一半」余数就是 (60 − 30) % 60 = 30。
- 24表里余数为 30 的歌有 2 首（高亮行），它们各能和当前这首配成一对，答案加 2，累计 5。
- 25把当前这首的余数 30 记进表（count[30] = 3），后面再来余数为 30 的歌时就能配上它。继续下一首。
- 26全部 7 首处理完，一共配成 5 对两首之和为 60 整数倍的歌曲。整个过程只扫一遍、只用一张余数计数表。
⚠️ 容易写错的地方
✗ 错：互补余数直接用 60 − r
✓ 对：要用 (60 − r) % 60
当 r = 0 时，60 − 0 = 60 越界；取模后 0 的互补还是 0
✗ 错：先把自己入表再查互补
✓ 对：必须先查互补、再把自己入表
先入表会把自己和自己错配，违反 i < j
✗ 错：只比较时长相等的歌
✓ 对：按「余数互补」配对
和为 60 整数倍只取决于余数互补，时长本身不必相等
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
count = [0] * 60
ans = 0
for t in time:
r = t % 60
ans += count[(60 - r) % 60]
count[r] += 1
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
vector<int> count(60);
int ans = 0;
for (int t : time) {
int r = t % 60;
ans += count[(60 - r) % 60];
count[r]++;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] count = new int[60];
int ans = 0;
for (int t : time) {
int r = t % 60;
ans += count[(60 - r) % 60];
count[r]++;
}
return ans;
}
}复杂度
时间
O(n)
每首歌只处理一次
空间
O(1)
计数表固定 60 个余数槽
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 总持续时间可被 60 整除的歌曲 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和「两数之和 LC1」是不是一回事？+
是同一套「边扫边用哈希找互补」的母题。LC1 找的互补是 target − x；本题找的互补是余数 (60 − r) % 60。都是「先查互补累加/记录，再把自己存入」的一遍扫描，O(n)。
为什么用长度 60 的数组而不用哈希表？+
余数只可能是 0..59 共 60 个值，用定长数组当计数表即可，比通用哈希表更快更省。这是「键域很小且连续」时的常见优化。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 总持续时间可被 60 整除的歌曲 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。