LeetCode每日一题3185---构成整天的下标对数目 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)。

提示：

1 <= hours.length <= 5 * 105
1 <= hours[i] <= 109

二、解题思路

这道题目最简单，也最容易想到的就是暴力解题，用两层for循环可以容易解题，但是当示例的数据量太时，暴力解法太耗时间，这里我们采用一种进阶的方法。
我们需要利用了模运算和哈希表思想来高效地判断两数之和是否能被 24 整除。下面我会从两个角度详细解释它的工作原理：
对于任意给定的小时数 hours[i]，我们关心的是它和另一数 hours[j] 是否能组合成 24 小时，即满足 hours[i] + hours[j] = 24 * k（k 是任意整数）。因为 24 是一个周期性的数，小时数的加法只需要考虑模 24 的余数情况。

如果我们能够找到两个数的余数之和为 24 或者能被 24 整除，那么这两个数的和也就能够被 24 整除。例如：

如果 hours[i] % 24 = 5，那么要使 hours[i] + hours[j] 为 24，hours[j] % 24 应该等于 19（因为 5 + 19 = 24）。
如果 hours[i] % 24 = 10，那么要使 hours[i] + hours[j] 为 24，hours[j] % 24 应该等于 14（因为 10 + 14 = 24）。

为了快速找到这些能组成 24 小时对的数，我们使用了一个长度为 24 的数组 count[]，它的作用类似于哈希表，记录每个模 24 余数出现的次数。

具体来说，算法按以下步骤工作：

遍历每个小时数，计算模 24 的余数： 对于每个元素 hours[i]，首先计算出 cur = hours[i] % 24，也就是当前小时数除以 24 后的余数。

• 计算与当前余数互补的值： 为了找到与当前小时数能够组成 24 的另一小时数，我们计算它的“互补余数” m = (24 - cur) % 24，即需要什么样的数与当前数相加能得到 24。
• 查找是否已经有互补的余数存在： 检查 count[m]，即互补余数 m 出现的次数。如果之前有过这样的余数 m，则可以和当前数组成对，因此把 count[m] 中的值加到 result 上。
• 更新当前余数的计数： 无论是否找到互补余数，都将当前余数 cur 的出现次数在 count[cur] 中自增，表示当前的小时数以后可能会和后面的数组成 24 小时对。

三、代码

long long countCompleteDayPairs(int* hours, int hoursSize) {long long  count[24]={0};long long  cur = 0;long long  result=0;long long  m=0;for(int i=0;i<hoursSize;i++){cur = hours[i];cur = cur % 24;m = (24 - cur)%24;result += count[m];count[cur]++;}return result;}