題目地址

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

題目描述

在歌曲列表中，第 i 首歌曲的持續(xù)時間為 time[i] 秒。
返回其總持續(xù)時間（以秒為單位）可被 60 整除的歌曲對的數(shù)量。形式上，我們希望索引的數(shù)字 i 和 j 滿足  i < j 且有 (time[i] + time[j]) % 60 == 0。

示例 1：
輸入：[30,20,150,100,40]
輸出：3
解釋：這三對的總持續(xù)時間可被 60 整數(shù)：
(time[0] = 30, time[2] = 150): 總持續(xù)時間 180
(time[1] = 20, time[3] = 100): 總持續(xù)時間 120
(time[1] = 20, time[4] = 40): 總持續(xù)時間 60
示例 2：
輸入：[60,60,60]
輸出：3
解釋：所有三對的總持續(xù)時間都是 120，可以被 60 整數(shù)。

提示：
1 <= time.length <= 60000
1 <= time[i] <= 500

思路

1. 暴力法, 算出所有對的和, 將其中和%60=0的對加起來. 這種辦法超時.
2. (A+B) % 60 == 0 ==> (A%60 + B%60) %60 == 0, 這樣我們可以將nums數(shù)組映射到一個長度為60的數(shù)組mods中, 索引就是%60后的值. 值就是%60后值為索引值的個數(shù).
   假設(shè)mods[i]= 2, mods[j] = 3, i+j=60.
   這種情況下和%60的對數(shù)等于 mods[i]和mods[j]的排列組合即mods[i]*mods[j].
   要注意mods[0]和mods[30]需要單獨處理
   mods[0]和mods[30]自身可以和另一個mods[0],mods[30]組合. 對數(shù)等于(n-1)!即(1~n-1)的等差數(shù)列求和.

題解

/**
 * 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);
    }
    /**
     * 執(zhí)行用時：2 ms, 在所有 Java 提交中擊敗了99.68%的用戶
     * 內(nèi)存消耗：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;
    }
}