Leetcode 1010. Pairs of Songs With Total Durations Divisible by 60 解法

 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，所有元素先除60 之後用一個字典來儲存位置

之後走一遍即可，本題基本上就是two sum的改變版。複雜度O(n)

歡迎參考下方python code

class Solution(object):
    def numPairsDivisibleBy60(self,time):
        """
        :type time: List[int]
        :rtype: int
        """
        h={}
        n=len(time)
        time=[i%60 for i in time]
        for i in range(n):
            if time[i] not in h:
                h[time[i]]=[i]
            else:
                h[time[i]].append(i)
        a=0
        for j in range(n):
            x=(-time[j])%60
            if x  in h:
                for i in h[x]:
                    if j>i:
                        a+=1
        return a