余数优化解法秒过力扣1010

问题解析力扣1010 题 “总持续时间可被 60 整除的歌曲” 要求统计数组中所有满足(time[i] time[j]) % 60 0的数对(i, j)的个数i j。直接暴力枚举会超时需利用余数性质优化。核心思路对每个时间t计算t % 60的余数r。若存在另一个数的余数r2满足(r r2) % 60 0则这两个数之和可被 60 整除。具体地若r 0需与余数为 0 的数配对。若r 30需与余数为 30 的数配对。其他情况需与余数为60 - r的数配对。使用哈希表数组或unordered_map记录每个余数出现的次数遍历时累加配对数量即可。C 代码实现class Solution { public: int numPairsDivisibleBy60(vectorint time) { vectorint remainderCount(60, 0); // 存储余数出现次数 int count 0; for (int t : time) { int r t % 60; if (r 0) { // 余数为0的数可与之前所有余数为0的数配对 count remainderCount[0]; } else { // 与余数为60-r的数配对 count remainderCount[60 - r]; } remainderCount[r]; // 更新当前余数出现次数 } return count; } };代码说明remainderCount数组用于记录每个余数0到 59出现的次数。遍历每个时间t计算余数r。根据r的值累加可配对的数对数量若r 0则当前数可与之前所有余数为 0 的数配对因为0 0 0可被 60 整除。否则当前数需与余数为60 - r的数配对因为(r (60 - r)) % 60 0。更新当前余数的计数确保后续数能正确配对。时间复杂度 O(n)空间复杂度 O(1)数组大小固定为 60。示例输入time [30,20,150,100,40]30 % 60 30remainderCount[30]初始为 0count 0remainderCount[30] 1。20 % 60 20需配对余数 40remainderCount[40]为 0count 0remainderCount[20] 1。150 % 60 30需配对余数 30remainderCount[30]为 1count 1remainderCount[30] 2。100 % 60 40需配对余数 20remainderCount[20]为 1count 1remainderCount[40] 1。40 % 60 40需配对余数 20remainderCount[20]为 1count 1remainderCount[40] 2。输出count 3对应数对(30,150)、(20,100)、(20,40)。参考来源❤️67❤️带新手一起刷力扣 (LeetCode)❤️代码有详细的注释❤️反思总结❤️67. 二进制求和力扣1010.总持续时间可被60整除的歌曲从导弹拦截到贪心算法LeetCode 1010题保姆级图解教程附C代码leetcode 409.最长回文串 C力扣67-二进制求和-C