刷LeetCode的时候我习惯先把“看起来简单”的题先做一遍因为这类题往往最容易在细节上翻车。1010这道题描述很短意思也很直白给定一个歌曲时长列表找出有多少对歌曲它们时长之和能被60整除。别看它难度标记是Easy我第一次提交就踩了超时的坑后面又踩了边界条件的坑。这篇文章就把这道题从暴力到最优的完整思路、代码实现、常见错法一次讲清楚顺便分享一些我在实际写题过程中的复盘心得给正在刷题的朋友一个参考。1. 题目解析与核心思路拆解1.1 题目到底在问什么题目给一个整数数组time每个元素代表一首歌的时长秒。要求返回一共有多少对(i, j)满足i j且(time[i] time[j]) % 60 0。举例来说如果输入是[30, 20, 150, 100, 40]那么30 150 180180能被60整除算一对20 40 60也能被60整除算一对100 20 120也能被60整除也算一对其他的组合不满足。所以输出是3。需要注意题里并没有说数组有序也没有说元素互不重复所以所有满足条件的下标组合都要计数。1.2 为什么第一反应是“哈希表配余数”如果先想到两层循环暴力枚举那说明思路方向没问题但这种做法的时间复杂度是 O(n²)。当数组长度达到几万甚至几十万时超时几乎是必然的。我们需要把问题转换成“余数配对”的思路两个数之和能被60整除本质上就是它们对60取模后的余数相加等于60或者两个余数都为0。换句话说设a time[i] % 60b time[j] % 60那么两个数能配对的充要条件是当a 0时b也必须为 0当a ! 0时b必须等于60 - a。有了这个等价关系问题就变得非常简单遍历数组用哈希表统计之前出现过的余数对于当前数查找它需要的“伴侣余数”已经出现了多少次把次数累加到答案里然后再将自己计入哈希表。1.3 复杂度对比暴力解法的时间复杂度是 O(n²)空间复杂度 O(1)。如果数组有10万个数最坏情况下要计算约50亿次加法取模即使每秒钟几亿次运算也要跑好几秒在实际的判题环境里妥妥超时。哈希表解法的时间复杂度降到 O(n)空间复杂度 O(60) 或 O(n)取决于实现方式。数组长度再大也只需遍历一次差距是数量级的。2. 为什么用“补数配对”比“整除判断”更优雅2.1 补数关系的数学原理这里有个容易犯迷糊的点为什么条件是b 60 - a而不是b 60 - a时还要考虑a b 0的情况因为取模结果的范围是 0 到 59所以a b只有两种可能等于 0或者等于 60。如果两个余数都在 1 到 59 之间两个正数相加不可能等于0所以只能是60。那就意味着当a在 1 到 59 之间时b只能是60 - a当a 0时b只能是 0因为任何非零余数和0相加都落在1到59之间无法被60整除。只有在a 0或b 0时才需要单独处理其他情况统一套用补数公式。2.2 长度为60的计数数组其实就够了多数题解会选择长度为60的数组因为余数只可能有60种取值。但我们也可以直接用哈希表存储余数到出现次数的映射。用数组和用哈希表有什么区别数组下标是固定的 0 到 59可以直接通过count[remainder]取值访问时间是 O(1)内存固定哈希表在余数分布稀疏时更省空间但在这个场景里余数最多60种省不了多少反而多一层哈希计算的开销从代码可读性上看数组法更直观也更容易查错。所以除非语言里数组初始化特别麻烦否则我建议直接上长度60的数组。2.3 处理“余数为0”的经典错法很多第一次做题的人会把代码写成这样for t in time: r t % 60 ans count[(60 - r) % 60] count[r] 1这里用(60 - r) % 60其实是一个很巧妙的写法。当r 0时60 - 0 60而60 % 60 0索引回到0正好满足“余数为0需要找余数为0”的规则。当r ! 0时(60 - r) % 60就等于60 - r因为60 - r的范围是1到59取模后不变。这个写法比强制分if r 0和else两条分支更简洁而且不容易漏条件。我第一次做这道题时用的是显式分支后来看到这个取模写法直接替换掉了。3. 完整实现与核心代码细节剖析3.1 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 ans这段代码只有几行但要理解它为什么能正确统计需要想清楚顺序问题当前歌曲只能与它之前的歌曲配对所以先查count再把当前歌曲累加进去如果先自增再查会把当前歌曲自己和自身配对导致计数多算但题目要求i j同一首歌不能和自己配对所以必须先查后加。整个流程走一遍示例[30, 20, 150, 100, 40]初始化count全0ans 0。遍历30r 30查count[(60 - 30) % 60] count[30]值为0将count[30]变为1遍历20r 20查count[(60 - 20) % 60] count[40]值为0将count[20]变为1遍历150150 % 60 30查count[(60 - 30) % 60] count[30]值为1答案加1将count[30]变为2遍历100100 % 60 40查count[(60 - 40) % 60] count[20]值为1答案加1将count[40]变为1遍历4040 % 60 40查count[(60 - 40) % 60] count[20]值为1答案加1将count[40]变为2。最终ans 3与预期一致。3.2 Java实现对比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; } }Java的写法基本和Python一样但有个地方要留意如果time数组很大ans可能超过int的最大值吗题目在LeetCode上给出的约束是1 time.length 6 * 10^4最多有n * (n - 1) / 2对组合大约是18亿对勉强低于Integer.MAX_VALUE约21.47亿。所以用int理论上没问题但如果你在本地测试时把数组长度加到10万就会溢出建议直接用long更稳妥。3.3 C 实现与性能考量class Solution { public: int numPairsDivisibleBy60(vectorint time) { vectorint count(60, 0); int ans 0; for (int t : time) { int r t % 60; ans count[(60 - r) % 60]; count[r]; } return ans; } };C的vectorint默认初始化为0不需要额外填充。如果追求极致性能可以把vector换成裸数组int count[60] {0};但差别在这个数据规模下几乎体现不出来。建议优先保证代码可读性。3.4 Go实现func numPairsDivisibleBy60(time []int) int { count : make([]int, 60) ans : 0 for _, t : range time { r : t % 60 ans count[(60-r)%60] count[r] } return ans }Go的数组默认零值也是0逻辑上的写法和上面几种语言没有区别。需要注意Go里%对负数取模会得到负值但这道题的输入全是正整数所以不用担心。4. 逐步推演与边界条件测试4.1 自己手写一遍完整的推演再找一个更复杂的例子手动推一下确认代码在边缘情况下的行为。假设输入为[60, 60, 60]。三个数的余数都是0第一首查count[0]为0然后count[0]变为1第二首查count[0]为1答案加1然后count[0]变为2第三首查count[0]为2答案加2然后count[0]变为3。答案总共是3手动枚举也确实是3对(0,1)、(0,2)、(1,2)。这说明相同余数连续出现时累加逻辑是自洽的。4.2 输入只有一个元素题目约束数组长度至少为1。如果只有一个元素循环里只会查一次count里全是0答案就是0。不需要额外判断。4.3 输入恰好都是余数互补的组合比如[10, 50, 10, 50]第一首10查count[50]0count[10]1第二首50查count[10]1答案1count[50]1第三首10查count[50]1答案2count[10]2第四首50查count[10]2答案4count[50]2。答案是4手动枚举所有对(0,1)、(0,3)、(2,1)、(2,3)确实是4对。程序没有问题。4.4 边界条件小结这道题的边界条件主要集中在余数为0和余数为30这两类特殊值。余数为0的情况前面已经分析过必须寻找余数为0的配对。余数为30的情况也容易让人困惑30 30 60也能被60整除所以余数30的配对对象是它本身。用(60 - 30) % 60 30可以正确处理。5. 三个常见错误与调试实录5.1 两层循环超时不是算法问题而是题目规模问题我最初做这题时第一版就是两层for循环写的ans 0 for i in range(len(time)): for j in range(i 1, len(time)): if (time[i] time[j]) % 60 0: ans 1 return ans逻辑完全正确示例测试也能过但提交后直接判超时。后来我特意去看了一下题目的数据范围发现数组最大长度是60000O(n²) 在最坏情况下大约要算 1.8e9 次循环在LeetCode的判题环境里基本不可能通过。这个教训让我养成了一个习惯写题之前先看数据范围快速估算复杂度是否在可接受范围内而不是直接开写。5.2 先更新计数导致多算这是另一个非常隐蔽的错法。如果把代码写成for t in time: r t % 60 count[r] 1 ans count[(60 - r) % 60]问题在于count[r]已经包含了当前元素自己。如果当前余数正好需要找自己比如余数是0或者30答案就会多算1。比如数组只有一个元素[60]正确输出应该是0但这种写法r 0先count[0] 1再查count[(60 - 0) % 60] count[0]得到1答案加1。输出变成了1错误很明显。所以顺序必须是先查后加。5.3 用布尔值而不是计数还有一次我把count设计成了set或布尔数组想当然地认为“出现过就够了”。但题目要求统计所有配对数量如果一个余数出现过多次它们分别都能配对那就必须计数。比如输入[20, 40, 20, 40]正确答案是4对但用布尔标记只能记录“20出现过”和“40出现过”最多算出一对直接丢掉了大量答案。正确做法是存出现次数每次配对时把次数全部累加进去。5.4 自测用例与调试技巧如果你写完代码后不确定对不对可以先跑这几个用例输入预期输出[30, 20, 150, 100, 40]3[60, 60, 60]3[10, 50, 10, 50]4[60]0[30, 30, 30]3一个长度为60000的全60数组1799970000最后一个用例需要解释一下如果有60000个60任意两首都能配对组合数就是60000 * 59999 / 2 1799970000。这个值接近int上限但没超过但如果你用Python整数随便存用Java/C记得确认变量类型是否够用。6. 从这道题延伸出的几个思考6.1 “先查后加”是一种通用套路这个“遍历当前元素先查询历史信息再把当前元素加入历史”的套路在处理“两两配对”类问题时非常常见。类似的题目包括 LeetCode 1两数之和、LeetCode 454四数相加 II本质上都是借助哈希表把暴力枚举压缩成单次遍历。区别在于这里钥匙是余数其他题钥匙可能是数值本身。6.2 如果不是60而是任意K怎么改如果把60换成别的数比如让总和能被K整除代码几乎不用动只需要把count的长度从60改成K把(60 - r) % 60改成(K - r) % K。比如 K 1 时所有余数都是0任意两首都配对答案应该是n * (n - 1) / 2。用公式(1 - 0) % 1在某些语言里会出现对0取模的问题因此实际写通用解法时要注意 K1 的特殊处理或者用(K - r) % K并确认语言对除零或取模零的行为。 Python和Java中x % 0会直接抛异常所以如果写通用函数必须单独处理 K1 的情况。6.3 时间复杂度的直觉判断法怎么快速判断 O(n²) 能不能过我自己的经验公式是如果 n 在 10^4 以内O(n²) 在大部分判题机上勉强能过当 n 达到 10^5 以上O(n²) 几乎必挂这时候至少要优化到 O(n log n) 或 O(n)。这道题 n 最大可取到 6 * 10^4两层循环的风险很高应该直接选 O(n) 方案。虽然 O(n²) 在最坏情况下也许能跑到几秒但算法题不能只看平均情况要看上限。既然有简单到几行的 O(n) 写法就不要赌判题环境了。6.4 工程上的应用联想播放列表与时间窗口统计在现实场景里这种“按模值分组再配对”的思想也能用到一些运营分析的场景。例如如果要统计一段时间内所有时长为整分钟的音频文件配对情况或分析直播间里观众停留时长能否凑成整数分钟的组合都可以使用类似思路。不过LeetCode题毕竟是抽象模型真实场景往往还有时间顺序、权重等其他条件这里仅作联想。7. 实操心得与后续扩展建议7.1 我在调试中觉得最有用的技巧遇到这种统计类问题千万不要只靠眼睛检查代码。把几个手算过的例子输入进去把每一轮count数组和ans的变化逐行打印出来比看十遍代码都有效。具体做法可以先写个带print的调试版def num_pairs_divisible_by_60_with_debug(time): count [0] * 60 ans 0 for t in time: r t % 60 need (60 - r) % 60 print(fcurrent{t}, r{r}, need{need}, count[need]{count[need]}) ans count[need] count[r] 1 print(fafter update, count[{r}]{count[r]}, ans{ans}) return ans这样你就能看到每一步配对数量是从哪里来的一旦某个用例结果不对马上能定位到是余数计算错、查询对象错还是更新顺序错。7.2 注意处理“返回类型”和“中间值溢出”LeetCode的原版函数返回类型是intJava和C在这道题内没问题但如果你把数据加强就不好说了。写算法题时习惯性考虑“最坏情况下中间变量会不会溢出”是个好习惯。Python虽然不会溢出但Java/C/Go都会尤其涉及计数的题目如果数量级到 10^5 甚至 10^6组合数会瞬间超过 2^31。判断不了的场景直接选用更大的类型最安全。7.3 补充一个更精巧的数学写法有些题解会把“先查后加”等价地写成“先累加再配对”的变形还有的会用乘法公式等遍历结束之后对每个余数r和60-r做组合数相乘最后加上余数0和余数30的组合数。这种方式代码如下def numPairsDivisibleBy60_math(time): count [0] * 60 for t in time: count[t % 60] 1 ans 0 # 余数为0自己和自己配对 ans count[0] * (count[0] - 1) // 2 # 余数为30自己和自己配对 ans count[30] * (count[30] - 1) // 2 # 其他余数r 和 60-r 互相配对只需要遍历一半 for r in range(1, 30): ans count[r] * count[60 - r] return ans这种方法需要单独处理r 0和r 30因为它们的配对对象是自己。如果套用count[r] * count[60-r]就会把同一对歌曲算两遍。先遍历数组做完统计再用组合数一次算出答案逻辑上也很清晰而且不容易出错。两种写法的复杂度一样区别在于第一种直观顺序感强第二种数学感更强代码最后几行能看出组合数学的意味。平时练习时建议两种都写一遍加深理解。7.4 后续还可以做的扩展尝试这道题做完以后我顺手看了一下讨论区里的其他解法有人提到可以用“同余类”思想把60替换成任意模数也有人把问题扩展到了三元组是否存在三个歌曲时长之和能被60整除。如果是三元组复杂度会怎么变还能不能继续用余数计数思考这样的扩展可以帮助你彻底掌握余数类题目的内在逻辑。我后来自己把K从60改成了7和13写了个通用函数跑了一遍随机测试对比暴力解结果一致对这类题的理解就又深了一层。如果你正在刷LeetCode的热门百题类似思路还会出现在“974. 和可被 K 整除的子数组”里。那道题是把余数用在连续子数组上核心完全是前缀和模K加哈希表。学完1010再去做974你会发现思路是连续递进的。