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

題目敘述

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

解題紀錄

暴力枚舉所有組合肯定會 timeout，必須往 O(n) 的方向想。

關鍵觀察：如果 x = 57，那麼 3, 63, 123... 都能與它湊成 60 的倍數。由於我們只關心「餘數」，可以用一個大小 60 的 array 來記錄每個 time[i] % 60 的出現次數。

每處理一個 x，只需查 array[(60 - x % 60) % 60] 就能知道在此之前有多少個值能與 x 湊成 60 的倍數，查完後再把 x % 60 寫入 array。

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;}();