3185.构成整天的下标对数目 II
【LetMeFly】3185.构成整天的下标对数目 II:哈希表
力扣题目链接:https://leetcode.cn/problems/count-pairs-that-form-a-complete-day-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
解题方法:哈希表
不论小时数为多少,最终结果都只与小时数取模24后的结果有关。因此我们可以开辟一个大小为24的哈希表,分别记录小时数模24后的结果数量。
方法一: 遍历一遍得到哈希表,$0$和$0$是一对,$12$和$12$是一对,其他$i$和$24-i$是一对。遍历哈希表得到答案数量。
方法二: 遍历过程中,假设这个数对$24$取模后的结果为$k$,则将答案数量加上$哈希表[(24 - k) % 24]$。
- 时间复杂度$O(len(hours))$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Go
1 |
|
Java
1 |
|
Python
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/143196224
3185.构成整天的下标对数目 II
https://blog.letmefly.xyz/2024/10/23/LeetCode 3185.构成整天的下标对数目II/