Pairs of Songs With Total Durations Divisible by 60 (M)
題目
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整除，求這樣的數對的個數，
思路
Hash，遍歷陣列，計算當前數除以60的余數R，如果R為0，在結果上加上之前余數為0的數的個數；如果R不為0，在結果上加上之前余數為60-R的數的個數，
代碼實作
Java
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int count = 0;
int[] remainders = new int[60];
for (int num : time) {
int remainder = num % 60;
if (remainder == 0) {
count += remainders[0];
} else {
count += remainders[60 - remainder];
}
remainders[remainder]++;
}
return count;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231831.html
標籤：其他
上一篇：面試前必知必會的二分查找及其變種