LeetCode|3185. 构成整天的下标对数目 II(day21)

作者：MJ昊

博客：掘金、CSDN等

公众号：程序猿的编程之路

今天是 昊 的算法之路第21天，今天分享的是LeetCode第3185题构成整天的下标对数目 II的解题思路。这是一道中等难度的题目，主要考察如何高效地统计两个元素之和为 24 的倍数的下标对，通过优化的算法减少时间复杂度。

题目描述简要回顾

给定一个整数数组hours，每个元素代表工作时长。求出有多少(i, j)对，使得hours[i] + hours[j]能被 24 整除（即(i < j)且 (hours[i] + hours[j]) % 24 == 0)。

解题思路

哈希表优化：
我们使用一个长度为 24 的数组cnt，记录每个时长对 24 取模后的频率。对于每个新的元素hour，我们计算它的模值，并查找之前是否存在能与当前模值配对的数值，使它们的和能被 24 整除。

代码实现：

var countCompleteDayPairs = function (hours) {
    let ans = 0;
    let cnt = new Array(24).fill(0); // 用于记录每个模值的频率
    for (let hour of hours) {
        // 找到与当前 hour % 24 互补的模值
        ans += cnt[(24 - (hour % 24)) % 24];
        // 更新当前模值的频率
        cnt[hour % 24]++;
    }
 return ans;
};

复杂度分析

时间复杂度： O(n)，遍历一遍数组即可。
空间复杂度： O(1)，使用固定大小的数组 cnt。

总结

该解法利用哈希表来优化配对查找，将时间复杂度从 O(n²) 降到了 O(n)，更高效地解决了问题。这种思想在很多求两数之和或配对问题中十分常见，是一种经典的空间换时间的策略。