LC.P1010[总持续时间可被60整除的歌曲]

方法一：数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] cnt = new int[60];
        int ans = 0;
        for (int i : time) {
            i %= 60;
            int j = (60 - i) % 60;
            // 先查询再更新，题目要求 i < j
            ans += cnt[j];
            ++cnt[i];
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(M)$，$M = 60$