[LeetCode] 1009. Complement of Base 10 Integer

[grandyang]

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 * 104
• 1 <= 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 同步地址:

#1010

类似题目：

Two Sum

参考资料：

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/discuss/256738/JavaC%2B%2BPython-Two-Sum-with-K-60

https://leetcode.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/discuss/256726/JavaPython-3-O(n)-code-w-comment-similar-to-Two-Sum

LeetCode All in One 题目讲解汇总(持续更新中...)