LeetCode 题解工作台
构成整天的下标对数目 II
给你一个整数数组 hours ，表示以 小时 为单位的时间，返回一个整数，表示满足 i 且 hours[i] + hours[j] 构成 整天 的下标对 i , j 的数目。 整天 定义为时间持续时间是 24 小时的 整数倍 。 例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以用一个哈希表或者一个长度为 的数组 来记录每个小时数模 的出现次数。 遍历数组 ，对于每个小时数 ，我们可以得出与 相加为 的倍数，且模 之后的数为 $(24 - x \bmod 24) \bmod 24$。累加这个数在哈希表或者数组中的出现次数即可。然后我们将 的模 的出现次数加一。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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 * 1051 <= hours[i] <= 109
解题思路
方法一：计数
我们可以用一个哈希表或者一个长度为 的数组 来记录每个小时数模 的出现次数。
遍历数组 ，对于每个小时数 ，我们可以得出与 相加为 的倍数，且模 之后的数为 。累加这个数在哈希表或者数组中的出现次数即可。然后我们将 的模 的出现次数加一。
遍历完数组 后，我们就可以得到满足题意的下标对数目。
时间复杂度 ，其中 为数组 的长度。空间复杂度 ，其中 。
class Solution:
def countCompleteDayPairs(self, hours: List[int]) -> int:
cnt = Counter()
ans = 0
for x in hours:
ans += cnt[(24 - (x % 24)) % 24]
cnt[x % 24] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of using hash maps for efficient counting.
- question_mark
Look for candidates who leverage the modulo operation correctly to check for complete day pairs.
- question_mark
Pay attention to candidates' ability to reduce complexity using hash lookups rather than brute force approaches.
常见陷阱
外企场景- error
Failing to handle large input sizes efficiently, especially if using a brute force approach that leads to O(n^2) time complexity.
- error
Incorrectly counting pairs by not properly handling modulo 24 for each element.
- error
Not accounting for cases where the complement exists multiple times in the array, which can lead to over-counting pairs.
进阶变体
外企场景- arrow_right_alt
What if the time array includes values beyond 24 hours?
- arrow_right_alt
How would you modify the approach to handle different lengths of arrays, such as very small arrays or arrays with many duplicate values?
- arrow_right_alt
Can the solution be optimized further if only one pair is needed rather than all pairs?