力扣每日打卡挑战 3184. 构成整天的下标对数目 I

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推

这个题目特别简单，因为数据范围只有100，直接两重循环，完全不存在超时的问题，一个枚举i，一个枚举j，然后判断是否和为24的倍数就可以了。不过因为hours数组的最大值是1e9，还有求和，所以为了保险起见避免爆int，我用了long long

时间复杂度O(n*n), 空间复杂度O(1)。

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

 前面只是上课前赶时间写的，而很明显这个题目应该还有可以优化的地方，平方的复杂度还是有点高了。那么有什么办法可以优化一下呢？可以这样想，我们的i已经确定了，那么要找的j就是固定加起来是24的倍数的。那是不是可以想办法记录一下每个数和哪些数加起来是24的倍数呢。当然可以，给每个数对24取余一下就可以了，而和它组成的24倍数的就是取余后和为24的。这一点应该能够理解。这样就得到了一个改进版的代码了，实际上这也就是哈希了

class Solution {
public:int countCompleteDayPairs(vector<int>& hours) {int len = hours.size();vector<vector<int> > vec(24);for (int i=0; i<len; i++){int mod = hours[i]%24;vec[mod].push_back(hours[i]);}int ans=0;for (int i=1; i<12; i++){ans += (vec[i].size())*(vec[24-i].size());}int mod0 = vec[0].size(), mod12 = vec[12].size();ans += mod0*(mod0-1)/2;ans += mod12*(mod12-1)/2;return ans;}
};

取余为0和取余为12的需要特判一下，因为和它们配对的数的取余值就是自己。

这样就把两重循环变成了一重循环，但增加了一个vec数组用来记录每个数取余后所在的位置。

时间复杂度O(n), 空间复杂度O(n)。

那么，还有办法可以继续优化吗？时间复杂度肯定是降不下去了，毕竟不管怎么改，总得遍历一次吧。但空间复杂度说不定还可以优化一下。

确实可以，我们可以注意到，我们虽然在vec里把每个数都存了起来，但实际上我们并没有用到它们。我们只是用到了数量。那么我们完全可以选择不存这些数，而只记录一下取余后的值的数量。

这样我们就得到了下一版的代码了

class Solution {
public:int countCompleteDayPairs(vector<int>& hours) {int len = hours.size();map<int, int> ma;for (int i=0; i<len; i++){ma[hours[i]%24]++;}int ma0=ma[0], ma12=ma[12];int ans = ma0*(ma0-1)/2;ans += ma12*(ma12-1)/2;for (int i=1; i<12; i++){ans += ma[i]*ma[24-i];}return ans;}
};

思路与之前一致，只是少存了没用的数了，顺便这里的map完全可以用一个数组代替，我只是太久没写代码了，用下map熟悉一下而已

时间复杂度还是O(n)，但空间复杂度降到了O(1)。

这应该就是最终版了，至少我想不到其他的优化方法了

翻了下力扣的题解，我又找到了一个优化方法。其实也不算优化吧，因为时空复杂度都不变，只不过也许可能大概常数因子会稍微小一点，因为把乘法换成了加法，也少了一次循环，但多了取余

class Solution {
public:int countCompleteDayPairs(vector<int>& hours) {int ans = 0;int cnt[24];memset(cnt, 0, sizeof(cnt));//也许换成循环会更快一点点？for (int h : hours){int mod = h%24;ans += cnt[(24-mod)%24];cnt[mod]++;}return ans;}
};

特别提醒一句，cnt[(24-mod)%24]里面的取余是必不可少的，不然mod为0的时候就会数组越界了。而且两个加法的顺序也不能换，不然就多算了