LeetCode【#1010】Pairs of Songs With Total Durations Divisible by 60

题目链接:

点击跳转

 

题目：

In a list of songs, the i-th 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 < jwith (time[i] + time[j]) % 60 == 0.

 

Example 1:

Input: [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: [60,60,60] Output: 3 Explanation: All three pairs have a total duration of 120, which is divisible by 60.

 

Note:

1 <= time.length <= 600001 <= time[i] <= 500

题目分析：

给定一个整型数组，里面每个数表示的对应这首歌的持续时间，我们需要找出能匹配的两首歌总共有多少对？

匹配的条件是：第二首歌必须是第一首歌之后，两首歌的总时间能被60整除。

 

解题思路：

一开始的思路，是暴力枚举，枚举第一首歌，然后第二首歌是枚举在第一首歌之后的所有情况，判断条件成立就 ans++ 。但这样子的时间复杂度是 O(n^2) 。题目中，数组长度 n<=6e+4，所以时间复杂度是 3.6e+9，这样子会超时。

因此上述暴力枚举的方法行不通。

如果两首歌时间之和要能被60整除，说明余数为0，那么假设第一首歌对60的余数是 a ，那么另一首歌的对60的余数为 60-a 才行。所以我们可以用一个长度为60的数组，下标刚好对应求余后的数，每次找到一个新的歌余数为 a，就看它前面对应余数为 60-a 的有多少首歌，即可以匹配为多少对。最后这首歌的余数对应的下标数组值 ++。

这样解决之后，我们只用遍历一次数组即可，所以时间复杂度是 O(n) ，但是需要了额外的空间开销。

 

AC代码：

class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { vector<int> res(60,0); int len = time.size(); int ans = 0; for(int i = 0;i < len;i++) { ans += res[(60-(time[i]`))`]; res[time[i]`]++; } return ans; } };