题目简介

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

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

提示：

1 <= time.length <= 6 * 104
1 <= time[i] <= 500

代码模板

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {

    }
};

分析

首先想到的是暴力求解。求出所有的两组歌曲长度和的情况，每个都用60取余，如果余数为0则满足条件，最后将所有情况相加即可。

比如示例一有三种情况，time[0]time[1],time[0]time[2],time[1]time[2]。如果情况为n的话，那需要遍历的次数就是 $$ (n+1)*(n+2)/2 $$ 即算法的时间复杂度为 $$ n^2 $$

参考代码如下：

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int a = 1, b = 2,sum=0;
        int s = time.size();
        while (a!=s)
        {
            if ((time[a - 1] + time[b - 1]) % 60 == 0)
            {
                sum++;
            }
            if (b == s)
            {
                a++;
                b = a + 1;
            }
            else
            {
                b++;
            }
        }
        return sum;
    }
};

寻求更优解

很显然，当你兴致盎然得进行提交之后，你会发现 $n^2 $ 的时间复杂度会使你获得一个红色的"超出时间限制"。那是因为time数组的长度可能很长，当数据较多时暴力求解还是过于复杂。我们需要设计一种更好的算法。

将问题转化为数学问题。本题可以简化为 求出所有能被60整除的两个数字的和 。那怎么样的两位数能被60整除呢？我们可以先将所有的数字除以60取余，得到范围在 0-59 之间的结果。并且我们可以将出现某个结果的数字的次数统计起来，比如有5个数字正好被60整除，那么结果0可以记为 5。此时我们可以分为三种情况。

如果两个数字的余数正好都是0，那么这两个数字加起来一定能被60整除。比如有五个这样的数字，运用高中学过的排列组合知识可以得到一共有 (5*4)/(2*1) = 10 种结果。

如果两个数字的余数正好都是30，那么这两个数字加起来也一定能被60整除。计算过程与上面那种情况类似。

如果一个数字的余数为n(0<n<=29)，要想这个数字和另一个数字加起来被60整除，那就应该找到数字60-n(30<n<=59)与其结合。计算过程与上方类似，如果20有3个，40有5个，那就应该有15种结果。

使用该算法的时间复杂度仅有 n。因为使用了一个长度为60的数组，算法的空间复杂度是 1 最终代码如下(注意整数溢出问题，使用 long long 或 int64_t)：

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> _time(60, 0);
        long long sum = 0;
      //遍历求余
        for (int cptime = 1; cptime <= time.size(); cptime++)
        {
            _time[time[cptime - 1] % 60]++;
        }
      //第一二种情况
        sum += ((long long)_time[0] * ((long long)_time[0] - 1)) / 2 + ((long long)_time[30] * ((long long)_time[30] - 1)) / 2;
      //第三种情况，注意数组中元素为0的情况
        for (int cptime = 1; cptime <= 29; cptime++)
        {
            if (_time[cptime] == 0 or _time[60 - cptime] == 0)
            {
                continue;
            }
            sum += (long long)_time[cptime] * (long long)_time[60 - cptime];
        }
      //累加完成后返回最终结果
        return sum;

    }
};

排列组合相关知识见高中数学选修三课本。另外，本题还可以利用哈希表相关知识求解。