$ cat ./coding/1010-pairs-of-songs-with-total-durations-divisible-by-60.md

────────────────────────────────────────────────────────────

1010. Pairs of Songs With Total Durations Divisible by 60

這一個題目的核心比較偏向數學，首先要先推導出以下這個關係。

$\begin{array}{l}(a+b)\\ bmod60=0\\ \\ rightarrow((abmod60)+(bbmod60))\\ bmod60=0\\ \\ rightarrow\\ beginequation\\ begincasesa\\ bmod60=0\\ textandb\\ bmod60=0\\ a\\ bmod60+b\\ bmod60=60\\ endcases\\ endequation\end{array}$

有了以上的關係式之後，我們就可以討論兩個狀況

\\begin{equation} \\begin{cases} b \\bmod 60 = 0 & \\text{if } a \\bmod 60 = 0\\ b \\bmod 60 = 60 - a\\bmod60 & \\text{if } a \\bmod 60 \\neq 0\\\\end{cases} \\end{equation} ParseError: Expected 'EOF', got '&' at position 50: … \\bmod 60 = 0 &̲ \\text{if } a …

這裡之後和 1. 2 Sum 的技巧有點類似，那就是在當下的位置時，我要找之前有沒有一個數字，可以和我一起組成滿足題目條件的數值。在 2 sum 的題目裡，我要找的是和我相反的數字，讓我可以組合為 0 或是組合為某一個值，這裡的情況是：

1. 目標是我找出兩個數字對 60 求於數為零
2. 第一種情況，目前的數字對 60 求於數為零，那在我之前的「所有」的數字，只要是求於數為零的情況下，都可以組合出滿足題目條件的組合（上述推導結論一）
3. 第二種情況，目前的數字對 60 求餘數不為零，那我要找的數字就是前面是否有一個數字，對 60 求餘數時，剛好等於 60 減去我當下對 60 求餘數的值（上述推導結論二）

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        table = defaultdict(int)
        ans = 0
        for t in time: 
            a = t % 60 
            if a == 0:
                target = 0
                ans += table[0]
            else:
                target = 60 - a
                ans += table[target]
            table[a] += 1                
        return ans

上述的判斷式可以更近一步精簡成下方的式子，不過可以看看就好，因為下面的簡化式不容易看出題目本身的邏輯，而且時間複雜度不變。

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        table = defaultdict(int)
        ans = 0
        for t in time: 
            target = (60 - t % 60) % 60
            ans += table[target]
            table[t % 60] += 1
        return ans

$ ls ./coding/ | grep -v 1010-pairs-of-songs-with-total-durations-divisible-by-60