WalkingSun

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

2019/07/31 leetcode 哈希

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

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

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

  示例 1：

输入：[30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整数：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：

输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。
 

提示：

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

题解

对时长取模（%60），取模的值进行计数存入hash数组，对其轮循，排列组合 $hash[$i]($hash[60-$i])，对于0或30的键值特殊处理$hash[$i]($hash[$i]-1)/2，所有排列的和即为最终的数量。

<?php
class Solution {

    /**
     * @param Integer[] $time
     * @return Integer
     */
    function numPairsDivisibleBy60($time) {
        $length = count($time);
        $ret = 0;
        
        //======= 暴力求解（超时了，效率过低） ======
        // for($i=0;$i<$length;$i++  ){
        //     for($j=$i+1;$j<$length;$j++){
        //         if(($time[$i]+$time[$j])%60==0){
        //             $ret++;
        //         }
        //     }
        // }
        
        //hash
        $hash = [];
        for($i=0;$i<$length;$i++){
            $hash[$time[$i]%60] = ($hash[$time[$i]%60]??0)+1;
        }
        
        for($i=0;$i<=30;$i++){
            if(!isset($hash[$i])) continue;
            if($i==0 ||$i==30){
                  $ret += $hash[$i]*($hash[$i]-1)/2; 
            }else{
                  $ret += $hash[$i]*($hash[60-$i]);
            }
          
        }
        
        
        return $ret;
    }
}

时间复杂度：O(n)

空间复杂度：O(n) 运用hash表

Search

    Table of Contents