LeetCode.1010-歌曲總長度可被60整除的對數

這是小川的第377次更新，第405篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第239題（順位題号是1010）。在歌曲清單中，第i首歌曲的持續時間為[i]秒。

傳回其總持續時間（以秒為機關）可被60整除的歌曲對的數量，即當

i <j

時，

(time[i] + time[j])％60 == 0

。

例如：

輸入：[30,20,150,100,40]

輸出：3

說明：三對總持續時間可被60整除：

(time[0] = 30，time[2] = 150)：總持續時間180

(time[1] = 20，time[3] = 100)：總持續時間120

(time[1] = 20，time[4] = 40)：總持續時間60

輸入：[60,60,60]

說明：所有三對的總持續時間為120，可被60整除。

注意：

• 1 <= time.length <= 60000
• 1 <= time[i] <= 500

02 第一種解法

暴力解法，使用兩層for循環，但是會逾時。

public int numPairsDivisibleBy60(int[] time) {
    int count = 0, n = time.length;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if ((time[i]+time[j])%60 == 0) {
                count++;
            }
        }
    }
    return count;
}
           

03 第二種解法

我們需要将時間複雜度降到

O(N)

，就得重新考慮

time

中的元素值特性。

例如

[30,20,150,100,40]

，其中30和150可以配對，20和100可以配對，20和40可以配對，這三對數之和都可以被60整除，那我們可以事先就将這些數簡化一步，對60取餘，得到

[30,20,30,40,40]

，新的數範圍是

[0,59]

，那麼隻要後面出現的數能在前面找到一個數，兩者互補（即兩者之和等于60的倍數），即

60-temp = temp2;

temp2

在

temp

的後面出現，變成僞代碼就是

60-time[i]%60

但是換到另外一個例子上來看，

[60,60,60]

，取餘後變成了

[0,0,0]

，再用60去減，發現沒有可以配對的數，那我們就再取餘一次，即

(60-time[i]%60)%60

，這樣就可以處理那些本身是60的倍數的數。

思路：先對

time

中的數用60進行取餘運算，使用一個

HashMap

，

key

為新數組的元素值，

value

為出現次數，周遊新數組中的元素

num

，找到

(60-num)%60

HashMap

中的

value

值，進行累加，最後輸出。

public int numPairsDivisibleBy602(int[] time) {
    for (int i=0; i<time.length; i++) {
        time[i] %= 60;
    }
    int count = 0;
    Map<Integer, Integer> map = new HashMap<Integer,Integer>();
    for (int num : time) {
        count += map.getOrDefault((60-num)%60, 0);
        map.put(num, map.getOrDefault(num, 0)+1);
    }
    return count;
}
           

04 第三種解法

思路和第二種解法一樣，将

HashMap

換成

int

數組。

public int numPairsDivisibleBy603(int[] time) {
    int[] count = new int[60];
    int result = 0;
    for (int num : time) {
        result += count[(60-num%60)%60];
        count[num%60]++;
    }
    return result;
}
           

05 小結

算法專題目前已連續日更超過七個月，算法題文章245+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，好看、留言、轉發就是對我最大的回報和支援！