You are given a list of songs where the ith song has a duration of time[i] seconds.
Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.
Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
Example 2:
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
Constraints:
1 <= time.length <= 6 * 1041 <= time[i] <= 500
这道题说是给了一个歌曲列表的每首歌的播放时长，现在让找出有多少对儿的歌曲，使得其播放时长之和是 60 的倍数，看到这里有没有觉得很眼熟，没错，其实本质还是一道 Two Sum 的题，来跟着博主一起大声念 ’平生不识 TwoSum，刷尽 LeetCode 也枉然‘。不过这里不是简单的判断两数之和是否存在，而是要求出所有的符合题意的个数。由于数组中可能出现重复数字，所以需要统计出每个数字出现的个数。另外，这道题有一个很好的 trick，利用到了余数的性质，若两个数之和可以被 60 整数，则对其先分别对 60 取余后，再相加之和，还是可以被 60 整数，这样就可以把数字都缩小到 [0, 59] 的范围内了。之后就是要找和可以被 60 整除的两个数字了，经典的 Two Sum 的思路是先确定一个数字，然后用目标和减去当前这个数字，就是要在 HashMap 中查找是否存在。若是两个数字不同，则总共的组合数就是两个数字的出现次数直接相乘，但是假如两个数字相同，则是个组合问题，比如在n个数字中任意选两个数字的情况有多少种，为 n(n - 1) / 2。这里两个数字相同有两种情况，一种是它们都是 60 的倍数，取余后都变成了0，另一种是它们都是 30，这样加起来就是 60 的倍数，这两种情况要单独计算。还有，就是要用一个 HashSet 记录已经处理过的数字，以免产生重复计算，参见代码如下：
解法一：
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
int res = 0;
unordered_set<int> visited;
unordered_map<int, int> timeCnt;
for (int t : time) ++timeCnt[t % 60];
for (auto &a : timeCnt) {
if (visited.count(a.first)) continue;
if (a.first % 60 == 0 || a.first == 30) {
res += (a.second - 1) * a.second / 2;
} else {
int target = 60 - a.first;
if (!timeCnt.count(target)) continue;
res += a.second * timeCnt[target];
visited.insert(target);
}
visited.insert(a.first);
}
return res;
}
};
其实有种更简洁的写法，不用在统计完了出现次数之后再计算，而是在统计的时候就直接累加了。这里没有用 HashMap，而是直接用了一个大小为 60 的数组，上面提到了通过对 60 取余，可以把数字都缩小到 [0, 59] 的范围内，对于每次遍历到的数字，加上能和其配对的数字的出现次数，方法是用 600 减去当前数字，然后对 60 取余。然后累加对 60 取余的次数，参见代码如下：
解法二：
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
int res = 0;
vector<int> cnt(60);
for (int t : time) {
res += cnt[(600 - t) % 60];
++cnt[t % 60];
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1010
类似题目：
参考资料：
https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
