目标
给你一个整数数组 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 * 10^5
- 1 <= hours[i] <= 10^9
思路
有一个整数数组 hours，返回 hours[i] + hours[j] % 24 == 0，i < j 的下标对的个数。
与昨天的题目 3184.构成整天的下标对数目I 相比，数据规模从 100 变成了 5 * 10^5。枚举下标对的时间复杂度为 O(C(n,2))，即 O(n^2)，肯定会超时。
题目并不要求输出具体的下标对，只需要计数即可。当枚举右端点时，如果可以直接获取到已访问过的元素中，能够与当前元素组成合法下标对的元素个数，那么整体的时间复杂度可以降为 O(n)。定义 cnt[m] 表示已访问过的元素中对 24 取余后值为 m 的元素个数。当枚举到元素 i 时，只需累加 cnt[24 - nums[i] % 24] 即可。
代码
/**
* @date 2024-10-23 10:16
*/
public class CountCompleteDayPairs3185 {
public long countCompleteDayPairs_v2(int[] hours) {
long res = 0L;
int[] cnt = new int[24];
int zeroCnt = 0;
for (int hour : hours) {
int m = hour % 24;
if (m == 0) {
res += zeroCnt;
zeroCnt++;
} else {
res += cnt[24 - m];
cnt[m]++;
}
}
return res;
}
}
性能
