Medium

题目描述

给你一个整数数组 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[i] + hours[j]) % 24 == 0，则配对 (i, j) 构成有效的整天。
  • 使用数组或映射，对于从左到右移动的每个索引 j，将答案增加 (24 - hours[j]) % 24 的计数，然后增加 hours[j] 的计数。

解题思路

这道题要求找出所有满足条件的配对数目，其中两个时间之和能被24整除。

核心思路：利用取模运算的性质。如果两个数的和能被24整除，那么它们对24的余数之和要么是0，要么是24。

具体分析：

  • 对于任意两个数 a 和 b，如果 (a + b) % 24 == 0，那么 (a % 24 + b % 24) % 24 == 0
  • 这意味着要么两个数对24的余数都是0，要么它们的余数相加等于24

算法步骤：

  1. 使用哈希表记录每个余数值出现的次数
  2. 遍历数组，对于每个元素：
    • 计算其对24的余数 r
    • 如果 r == 0，需要找另一个余数也为0的数
    • 如果 r != 0，需要找余数为 24 - r 的数
    • 将当前已找到的匹配数累加到结果中
    • 更新当前余数的计数

这种方法只需要一次遍历，时间复杂度为O(n)，空间复杂度为O(1)（因为余数最多只有24种）。

推荐解法：哈希表计数法，既高效又简洁。

代码实现

class Solution {
public:
    long long countCompleteDayPairs(vector<int>& hours) {
        long long result = 0;
        unordered_map<int, int> count;
        
        for (int hour : hours) {
            int remainder = hour % 24;
            int target = (24 - remainder) % 24;
            
            result += count[target];
            count[remainder]++;
        }
        
        return result;
    }
};

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        result = 0
        count = {}
        
        for hour in hours:
            remainder = hour % 24
            target = (24 - remainder) % 24
            
            result += count.get(target, 0)
            count[remainder] = count.get(remainder, 0) + 1
        
        return result

public class Solution {
    public long CountCompleteDayPairs(int[] hours) {
        long result = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        foreach (int hour in hours) {
            int remainder = hour % 24;
            int target = (24 - remainder) % 24;
            
            if (count.ContainsKey(target)) {
                result += count[target];
            }
            
            if (count.ContainsKey(remainder)) {
                count[remainder]++;
            } else {
                count[remainder] = 1;
            }
        }
        
        return result;
    }
}

var countCompleteDayPairs = function(hours) {
    let result = 0;
    const count = new Map();
    
    for (const hour of hours) {
        const remainder = hour % 24;
        const target = (24 - remainder) % 24;
        
        result += count.get(target) || 0;
        count.set(remainder, (count.get(remainder) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是数组长度，只需遍历一次数组
空间复杂度O(1)，哈希表最多存储24个不同的余数值

相关题目