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.
Solution
我们用 \(unordered\_map\) 来统计余数，如果 \((t[i]+t[j])\%60=0\), 那么意味着余数的和为 \(60\). 所以直接利用组合数即可
点击查看代码
class Solution {
private:
unordered_map<int,int> mp;
public:
int numPairsDivisibleBy60(vector<int>& time) {
int n = time.size();
long long ans=0;
for(int i=0;i<n;i++){
mp[time[i]%60]++;
}
for(int i=0;i<=30;i++){
if(i==0|| i==30){
if(mp[i]==2)ans++;
if(mp[i]>2)ans+=(long long)(mp[i]-1)*mp[i]/2;
}
else{
ans+= (long long)(mp[i]*mp[60-i]);
}
}
return ans;
}
};