Medium

题目描述

给你一个歌曲列表，其中第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望下标数量 i, j 使得 i < j 且 (time[i] + time[j]) % 60 == 0。

示例 1：

输入：time = [30,20,150,100,40]
输出：3
解释：三对歌曲的总持续时间可被 60 整除：
(time[0] = 30, time[2] = 150)：总持续时间 180
(time[1] = 20, time[3] = 100)：总持续时间 120
(time[1] = 20, time[4] = 40)：总持续时间 60

示例 2：

输入：time = [60,60,60]
输出：3
解释：所有三对歌曲的总持续时间都是 120，可以被 60 整除。

提示：

  • 1 <= time.length <= 6 * 10^4
  • 1 <= time[i] <= 500

解题思路

这道题的关键在于理解模运算的性质。如果两个数的和能被60整除，那么它们对60取模的结果之和也能被60整除。

解题思路：

  1. 暴力解法：双重循环遍历所有配对，时间复杂度O(n²)，在数据规模较大时会超时。

  2. 哈希表优化（推荐）：利用余数互补的性质进行优化。对于每个歌曲时长t，我们只关心t % 60的值。如果两个余数r1和r2满足(r1 + r2) % 60 == 0，那么r2 = (60 - r1) % 60。

具体实现步骤：

  • 创建一个长度为60的数组count，记录每个余数值出现的次数
  • 遍历歌曲列表，对于每首歌曲：
    • 计算当前歌曲的余数remainder = time[i] % 60
    • 计算需要配对的余数target = (60 - remainder) % 60
    • 将count[target]加到结果中（这些是之前遍历过的能与当前歌曲配对的歌曲数）
    • 将count[remainder]增加1

特殊情况处理：

  • 当remainder为0时，target也为0，需要与其他余数为0的歌曲配对
  • 当remainder为30时，target也为30，需要与其他余数为30的歌曲配对

这种方法时间复杂度O(n)，空间复杂度O(1)，是最优解法。

代码实现

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> count(60, 0);
        int result = 0;
        
        for (int t : time) {
            int remainder = t % 60;
            int target = (60 - remainder) % 60;
            result += count[target];
            count[remainder]++;
        }
        
        return result;
    }
};

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        count = [0] * 60
        result = 0
        
        for t in time:
            remainder = t % 60
            target = (60 - remainder) % 60
            result += count[target]
            count[remainder] += 1
            
        return result

public class Solution {
    public int NumPairsDivisibleBy60(int[] time) {
        int[] count = new int[60];
        int result = 0;
        
        foreach (int t in time) {
            int remainder = t % 60;
            int target = (60 - remainder) % 60;
            result += count[target];
            count[remainder]++;
        }
        
        return result;
    }
}

/**
 * @param {number[]} time
 * @return {number}
 */
var numPairsDivisibleBy60 = function(time) {
    const count = new Array(60).fill(0);
    let result = 0;
    
    for (const t of time) {
        const remainder = t % 60;
        const target = (60 - remainder) % 60;
        result += count[target];
        count[remainder]++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历一次数组，每次操作为O(1)
空间复杂度O(1)使用固定大小60的数组存储计数

相关题目