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

You are given a list of songs where the ith song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Constraints:
1 <= time.length <= 6 * 104
1 <= time[i] <= 500

总持续时间可被 60 整除的歌曲。

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。

返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i 和 j 满足 i < j 且有 (time[i] + time[j]) % 60 == 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

其实把对 60 取模这个动作拿掉，你会发现这个题跟 two sum 几乎是一样的，所以思路也是类似去解决 two sum 一样的思路。对于两个数相加之后取模的操作，满足如下规则

(A + B) % 60 == (A % 60) + (B % 60)

这里我提供两种实现方式，但是核心思想还是跟 two sum 类似。

第一种，我们还是创建一个 hashmap，每当遇到一个数字 num 的时候，我们找一下另一个能和当前 num 组成配对的数字是否存在。潜在的配对数字是 (60 - num % 60) % 60。如果有就说明有合法的 pair。这个公式(60 - num % 60) % 60有一点技巧，处理了两个 corner case，30 + 30 和 0 + 60。首先 num % 60 就确保了可以把 num 变成一个小于 60 的数字，那么60 - num % 60也一定小于 60。为什么要再次对(60 - num % 60)取模60是为了处理 0 和 60 这种pair。

复杂度

时间O(n)
空间O(60) - O(1)

代码

Java实现一

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int t : time) {
            int comp = (60 - t % 60) % 60;
            res += map.getOrDefault(comp, 0);
            map.put(t % 60, map.getOrDefault(t % 60, 0) + 1);
        }
        return res;
    }
}

Java实现二

class Solution {
	public int numPairsDivisibleBy60(int[] time) {
		int[] map = new int[60];
		int res = 0;
		for (int t : time) {
			res += map[(60 - t % 60) % 60];
			map[t % 60]++;
		}
		return res;
	}
}

相关题目

1010. Pairs of Songs With Total Durations Divisible by 60
2453. Destroy Sequential Targets
3184. Count Pairs That Form a Complete Day I