Last Updated on 2022-01-02 by Clay
題目
You are given a list of songs where the ith song has a duration oftime[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 indicesi,jsuch thati < jwith(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
我們有一串歌曲列表的歌曲時間 time，第 i 首歌的時間長度為 time[i]。
我們要找出總時間長度可以被 60 秒整除的一對歌曲（也就是 time[i] + time[j] 可以被 60 整除），並返回歌曲列表中究竟有多少對這樣的歌曲組合。
解題思路
這題給我的感覺跟經典的 Two Sum 很像（可以參考 LeetCode: 1-Two Sum 解題紀錄），所以我也按照這樣的思路下去解題。
（順帶一提，一開始我想測試 O(n^2) 的 Brute Force 到底會花多少時間，結果直接超過時間限制，所以那個就不記錄了。）
宣告一組列表，引數想像成跟 60 秒的差距（所以只會有 0 - 59），儲存的數值一開始皆為 0，只要有跟 60 秒的差距正好為引數的歌曲，便會將該引數的數值加一。
依序讀出歌曲列表的秒數，並搜尋差距秒數紀錄在列表中的數量，並將其計數。如此一來在讀完全部的歌曲列表後，便能剛好找出所有秒數可被 60 整除的歌曲對。
複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
空間複雜度之所有只有 O(1) 是因為宣告的列表長度就是固定為 60，不會再增加。
C++ 範例程式碼
class Solution {
public:
int numPairsDivisibleBy60(vector<int>& time) {
// Init
int count = 0;
vector<int> losses(60, 0);
// Iteration
for (int i=0; i<time.size(); ++i) {
int loss = time[i] % 60;
int lack = (60 - loss) % 60;
count += losses[loss];
++losses[lack];
}
return count;
}
};Python 範例程式碼
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
# Init
count = 0
losses = [0 for _ in range(60)]
# Iteration
for t in time:
t = t % 60
loss = (60-t) % 60
count += losses[t]
losses[loss] += 1
return count