题目地址

https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/

题目描述

在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i 和 j 满足  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

思路

1. 暴力法, 算出所有对的和, 将其中和%60=0的对加起来. 这种办法超时.
2. (A+B) % 60 == 0 ==> (A%60 + B%60) %60 == 0, 这样我们可以将nums数组映射到一个长度为60的数组mods中, 索引就是%60后的值. 值就是%60后值为索引值的个数.
   假设mods[i]= 2, mods[j] = 3, i+j=60.
   这种情况下和%60的对数等于 mods[i]和mods[j]的排列组合即mods[i]*mods[j].
   要注意mods[0]和mods[30]需要单独处理
   mods[0]和mods[30]自身可以和另一个mods[0],mods[30]组合. 对数等于(n-1)!即(1~n-1)的等差数列求和.

题解

/**
 * Created by zcdeng on 2021/2/23.
 */
public class NumPairsDivisibleBy60 {
    public static void main(String[] args) {
        int[] nums = {418,204,77,278,239,457,284,263,372,279,476,416,360,18};
        int result = numPairsDivisibleBy60(nums);
        System.out.println(result);

        result = numPairsDivisibleBy60V2(nums);
        System.out.println(result);
    }
    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了99.68%的用户
     * 内存消耗：44 MB , 在所有 Java 提交中击败了35.55%的用户
     */
    private static int numPairsDivisibleBy60V2(int[] nums) {
        int[] mods = new int[60];
        for (int i=0; i<nums.length; i++) {
            mods[nums[i] % 60] += 1;
        }
        int result = (mods[0] - 1) * mods[0] / 2;
        for (int i=1,j=mods.length-1; i<j; i++,j--) {
            result += mods[i] * mods[j];
        }
        result += (mods[30] - 1) * mods[30] / 2;
        return result;
    }
    /**
     * 超时
     */
    private static int numPairsDivisibleBy60(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        int result = 0;
        for (int i=0; i<nums.length; i++) {
            int num = nums[i];
            for (int j=i+1; j<nums.length; j++) {
                if ((num + nums[j]) % 60 == 0) {
                    result++;
                }
            }
        }
        return result;
    }
}