Easy

题目描述

给你一个整数数组 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 <= 100
  • 1 <= hours[i] <= 10^9

解题思路

这道题要求找出数组中所有满足 i < j 且 hours[i] + hours[j] 是 24 的整数倍的下标对数量。

思路分析：

由于题目要求的是两数之和为 24 的整数倍，我们可以利用模运算的性质。如果 (a + b) % 24 == 0，那么 a % 24 + b % 24 要么等于 0，要么等于 24。

方法一：暴力枚举 最直接的方法是枚举所有可能的下标对 (i, j)，其中 i < j，然后检查 (hours[i] + hours[j]) % 24 是否等于 0。时间复杂度为 O(n²)。

方法二：哈希表优化（推荐） 我们可以利用模运算的性质进行优化。对于每个 hours[i]，计算 hours[i] % 24，然后在哈希表中查找能与之配对形成 24 整数倍的余数。具体来说：

  • 如果 hours[i] % 24 == 0，那么需要找另一个余数也为 0 的数
  • 否则需要找余数为 24 - (hours[i] % 24) 的数

由于题目数据规模较小（n ≤ 100），两种方法都能通过，但哈希表方法在理论上更优。

代码实现

class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int count = 0;
        int n = hours.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((hours[i] + hours[j]) % 24 == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        count = 0
        n = len(hours)
        
        for i in range(n):
            for j in range(i + 1, n):
                if (hours[i] + hours[j]) % 24 == 0:
                    count += 1
        
        return count

public class Solution {
    public int CountCompleteDayPairs(int[] hours) {
        int count = 0;
        int n = hours.Length;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((hours[i] + hours[j]) % 24 == 0) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var countCompleteDayPairs = function(hours) {
    let count = 0;
    for (let i = 0; i < hours.length; i++) {
        for (let j = i + 1; j < hours.length; j++) {
            if ((hours[i] + hours[j]) % 24 === 0) {
                count++;
            }
        }
    }
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²)
空间复杂度O(1)

相关题目