发表于 2024.06.02

• 该题目本质是统计数对(a, b)的个数，其中(a + b) % 60 == 0。由于(a + b) % 60 == 0等价于(a % 60 + b % 60) % 60 == 0，我们可以使用一个哈希表来存储前面已处理的数字模60后结果的计数，然后遍历元素b，累加哈希表中(60 - b % 60) % 60的计数即可。也可以先计数后，再遍历哈希表中的1-29的数字，累加count[i] * count[60 - i]，而对于i为1或者30的情况，则使用组合公式C(i, 2) = count[i] * (count[i] - 1) // 2来计算。

  from collections import defaultdict
  
  
  class Solution:
      def numPairsDivisibleBy60(self, time: List[int]) -> int:
          # (a + b) % 60 == a % 60 + b % 60
          # for 150, 150 % 60 = 30, 我们需要找到%60后为20的数字, 仅需要存储余数为20的数字计数即可, 无需对所有的数字进行计数
  
          mod_cnt = [0] * 60  # 存储的是 时间%60 的计数
          ans = 0
          for duration in time:
              duration %= 60
              ans += mod_cnt[(60 - duration) % 60]
              mod_cnt[duration] += 1
          return ans

  官解中，先计数后计算结果的做法：

  class Solution:
      def numPairsDivisibleBy60(self, time: List[int]) -> int:
          cnt = [0] * 60
          for t in time:
              cnt[t % 60] += 1
          res = 0
          for i in range(1, 30):
              res += cnt[i] * cnt[60 - i]
          res += cnt[0] * (cnt[0] - 1) // 2 + cnt[30] * (cnt[30] - 1) // 2
          return res

• LC 题目链接