2024-10-23-leetcode每日一题-构成整天的下标对数目 II

题目描述

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]

输出： 2

解释：

构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]

输出： 3

解释：

构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

解题思路

使用一个长度为24的mod数组存储hours余24的余数，记录余数为0-23的个数，其中余数为0的数本身就是24的倍数，是可以直接凑成整天的，只需要从余数为零的总个数（假设为n）中使用排列数取出两个就能组成一对，即Cn2。对于剩下的数据，余数为1的可以和余数为23的凑成一对，余数为2的可以和余数为22的凑成一对，以此类推，可以计算出所有的个数。注意数据范围，否则会爆RE。

AC代码

class Solution {

public:

    long long countCompleteDayPairs(vector<int>& hours) {

        long long ans = 0;

        long long mod[24];

        memset(mod, 0, sizeof mod);

        for(auto x: hours)

            mod[x % 24] ++;

        for(int i = 1; i < 24, i != 12; i ++)

            ans += mod[i] * mod[24 - i];

        ans += mod[0] * (mod[0] - 1) / 2;

        ans += mod[12] * (mod[12] - 1) / 2;

        return ans;

    }

};