1010. Pairs of Songs With Total Durations Divisible by 60

问题：

给出一列歌曲所花时间的数组。

求任意两首歌合起来时间是60分钟的倍数的组队pair数。

Example 1:
Input: [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: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60. 

Note:
1 <= time.length <= 60000
1 <= time[i] <= 500

　　

解法：

遍历数组，依次读入一个元素，

查看已遍历过的元素中，是否存在与当前元素互补（和=60倍数）的元素，假设有n个，那么到当前元素为止，已经有n个pair了。

（其实感觉思想都是看当前状态下的一个结果，思想很像DP：注重某个状态）

假设遍历到的当前元素时间为 t

那么我们要找的互补元素为：(t+X)%60=0

t%60+X%60=60

X%60=60-t%60

所以，我们用数组c[i]来记录，已遍历过数组元素中，被60除，余 i 的个数。

当遍历到 t 的时候，我们得到的互补元素个数即为 c[60-t%60]

⚠️ 注意：这里当 t=60时，会访问c[60]，我们设定数组index：0～59，

因此，我们应该访问c[0]，上述式子 c[60-t%60] 转化为-> c[(60-t%60)%60]

同时将当前的元素更新到数组c中，c[t%60]++

代码参考：

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int res=0;
        int c[60]={0};
        for(int t:time){
            res+=c[(60-t%60)%60];
            c[t%60]++;
        }
        return res;
    }
};