leetcode 1010. Pairs of Songs With Total Durations Divisible by 60 [Medium]

2022-01-02 103 words One minute

Contents

題目敘述

在一個陣列中找出兩兩相加是 60 的倍數的組合數。

解題紀錄

這個題目如果純粹的硬是把所有的組合都加過一次，一定會 time out，所以基本上要從 O(n) 的作法去嘗試。

假設 x = 57，那相加 3, 63 ... 都可以湊到 60 的倍數，所以我們只要用一個大小 60 的 array 來存 time[i] % 60 的結果就好了，今天 x = 57 的情況我們只要去 array 中查找 array[60 - 57 % 60] = array[3] 就可以獲得在此之前所有曾經出現過可以跟 57 湊成 60 倍數的資料了。

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int cnt = 0;
        int m[60] = {0};
        
        for (int i = 0; i < time.size(); ++i) {
            cnt += m[time[i]%60 == 0 ? 0 : 60 - time[i]%60];
            m[time[i]%60]++;
        }
        return cnt;
    }
};
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();