LeetCode 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：

输出： 2

解释：

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

示例 2：

输出： 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++

/*
0 0
1 23
2 22
...
11 13
12 12
*/
typedef long long ll;
class Solution {
public:
    ll countCompleteDayPairs(vector<int>& hours) {
        ll bin[24] = {0};
        for (int t : hours) {
            bin[t % 24]++;
        }
        ll ans = bin[0] * (bin[0] - 1) / 2 + bin[12] * (bin[12] - 1) / 2;
        for (int i = 1; i < 12; i++) {
            ans += bin[i] * bin[24 - i];
        }
        return ans;
    }
};

Go

package main

func countCompleteDayPairs(hours []int) int64 {
    bin := make([]int64, 24)
    var ans int64
    for _, t := range hours {
        ans += bin[(24 - t % 24) % 24]
        bin[t % 24]++
    }
    return ans
}

Java

class Solution {
    public long countCompleteDayPairs(int[] hours) {
        long[] bin = new long[24];
        for (int t : hours) {
            bin[t % 24]++;
        }
        long ans = bin[0] * (bin[0] - 1) / 2 + bin[12] * (bin[12] - 1) / 2;
        for (int i = 1; i < 12; i++) {
            ans += bin[i] * bin[24 - i];
        }
        return ans;
    }
}

Python

from typing import List

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        bin = [0] * 24
        for t in hours:
            bin[t % 24] += 1
        ans = bin[0] * (bin[0] - 1) // 2 + bin[12] * (bin[12] - 1) // 2
        for i in range(1, 12):
            ans += bin[i] * bin[24 - i]
        return ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143196224